不确定性与多项式时间可验证性

Question

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

Answer 1

首先，让我们证明可以在多项式时间内验证的任何事物都可以在不确定的多项式时间内求解。假设您有一些算法P（x，y）决定y是否验证x，并且P在某个常数k的时间O（| x | ^k）中运行。该算法的运行时是x的多项式，这意味着它只能查看y的多项式。然后，您可以构建此不确定的多项式时间算法来解决问题：

1. 不确定地猜出长度为O（| x | ^k）的字符串y。
2. 确定地运行P（x，y）并输出其所说的内容。

这在不确定的多项式时间内运行，因为y在不确定的多项式时间内构造，然后P（x，y）在多项式时间内运行。如果存在验证x的y，则该计算机可以不确定地猜测它。否则，无法猜测，机器将输出NO。

另一个方向比较棘手。假设有一个不确定性算法P（x）在某个常数k的不确定性时间O（| x | ^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是具有多项式时间验证器的语言类别。