P NP和NP完全闭锁？

Question

这是我在堆栈溢出中找到的一个答案。

NP是一个复杂的类，它表示所有决策问题的集合，对于这些问题，答案为“是”的实例都有可以在多项式时间内验证的证明。 这意味着，如果有人给我们一个问题的实例和一个证明(有时被称为证人)的答案是肯定的，我们可以检查它是否正确的多项式时间。

我的问题是，在多项式时间内，谁是检查解是否正确的“我们”？它是一个程序还是字面上的意思是一个人坐下来，并解决它在纸上？

Answer 1

在经典定义中，它是图灵机。我相信我们今天使用的计算机在复杂性理论意义上与图灵机差不多(一个是多项式时间，另一个是多项式时间)，参见：machines。