complexity-theory - 非确定性与多项式时间可验证性

Question

我读过NP问题在多项式时间内是可验证的，或者等效地，可以通过非确定性图灵机在多项式时间内解决。为什么这些定义是等价的？

Answer 1

首先，让我们证明任何可以在多项式时间内验证的东西都可以在非确定性多项式时间内解决。假设你有一些算法 P(x, y) 来决定 y 是否验证 x，并且 P 在时间 O(|x| ^k ) 中运行某个常数 k。该算法的运行时间是 x 中的多项式，这意味着它只能查看 y 的多项式许多位。然后你可以构建这个解决问题的非确定性多项式时间算法：

1. 不确定地猜测长度为 O(|x| ^k ) 的字符串 y。
2. 确定性地运行 P(x, y) 并输出它所说的任何内容。

这在非确定多项式时间内运行，因为 y 是在非确定多项式时间内构造的，而 P(x, y) 然后在多项式时间内运行。如果存在验证 x 的 y，则这台机器可以不确定地猜测它。否则，无法猜测，机器将输出 NO。

另一个方向更棘手。假设有一个非确定性算法 P(x) 在非确定性时间 O(|x| ^k ) 中运行某个常数 k。这种非确定性算法在每一步都从 c 个不同选项中选择下一步做什么。因此，您可以编写一个验证程序 Q(x, y)，其中 y 编码在计算 P 的每个步骤中要做出的选择。然后它可以模拟 P(x)，查看在 y 中编码的选择以确定哪一步采取下一步。这将在确定性时间 O(|x| ^k ) 内运行，因为它只是完成了非确定性计算中的所有步骤。

希望这可以帮助！

Answer 2

也许这个例子给出了一些提示：

变量的给定L = {w : expression w is satisfiable} 和时间：n

• 猜测变量的赋值O(n)
• 检查这是否是一个令人满意的任务O(n)
• 总时间：O(n)

可满足性问题是一个 NP 问题且难以处理，但由于每个猜测的线性时间复杂度这一事实，它被广泛用于计算应用程序。

NP 类旨在隔离多项式时间“可验证性”的概念。NP 是具有多项式时间验证器的语言类别。