complexity-theory - 在复杂度类 P 中，接受=决定。为什么不是NP？

Question

假设某个问题 L 属于复杂度类 P。那么有一些多项式时间算法 A 来决定该问题。我们有以下定理：如果 A 接受 L，则 A 决定 L。

证明通过注意如果 A 在多项式时间内运行，那么有一些非负常数 c, k 使得 A 的运行时间是 cn^k 其中 n 是输入 L 的大小。所以我们可以构造一个多项式时间算法 A'，如果 A 在 time<= cn^k 中返回 1，则调用 A 并返回 1，如果 A 的返回时间超过 cn^k，则返回 0。通过这样做，我们注意到如果 A 试图进入一个无限循环，那么 A' 会在 poly time 中停止该过程并返回 0，这意味着 A' 拒绝 L 的互补。

我的问题是：为什么这个证明对复杂类 NP 不起作用？我们能不能只说如果 L 在 NP 中，那么有一个非确定性的多时间算法 A 决定了 L，所以只定义 A' 如上？

标签： complexity-theorynpnp-complete

Answer 1

“决定”一个问题意味着能够判断给定字符串是否是该语言。如果字符串不在 NP 语言中，则在声明字符串不在语言中之前，没有多项式时间可以等待接受失败，这会使您的算法站不住脚。

对于 P 中的语言，您不知道“多项式时间量”实际上是什么，但您确实知道您的算法将在有限时间内终止任何输入。但是对于 NP，测试不是语言的输入可能永远不会终止，所以你永远无法判断你的输入是不是语言，或者你只是没有等待足够长的时间。