证明P <= NP

Question

正如大多数人知道的那样，P= NP是未经证实的，而且似乎不太可能是真的。证明将证明P <= NP和NP <= P，尽管其中只有一个是困难的。

根据定义，p <= NP几乎是真的。事实上，这是我唯一知道如何表述P <= NP的方法。这是很直观的。你如何证明P <= NP呢？

Answer 1

我认为你基本上已经在评论中回答了自己的问题:一个满足P定义的问题也满足NP的定义。

引用维基百科的话：

All problems in P are in NP

它所指的证书是解的多项式时间验证；正如您所说，您可以在多项式时间内在P中解决问题，因此您将有一个在多项式时间内经过验证的解，因此它在NP中。

Joey Adams的答案是第二种解释，根据(非)确定性图灵机的可解性。有关NP定义的更多说明，请参阅wikipedia article。

我认为你应该注意的是，证明非常简单的事实并不意味着它不是证明。“根据定义”是一个完全有效的逻辑步骤。

Answer 2

NP中的每个问题都是在多项式时间内由一个不确定的图灵机解决的。(根据定义*)

P中的每个问题都由一个确定性图灵机在多项式时间内解决。(根据定义)

每个确定性图灵机也是一个非确定性图灵机。(显然)

因此，P中的每个问题都是在多项式时间内由一个不确定的图灵机解决的。

因此，P中的每个问题都是NP中的问题。因此，P⊆NP。

*让我们读一读NP上的Wikipedia article：

在等价的形式定义中，NP是可由非确定性图灵机在多项式时间内求解的决策问题的集合。

没有必要在这么简单的推理中引入关于多项式验证的东西。

Answer 3

非确定性计算机不能简单地调用它的非确定性，而是像确定性计算机一样工作，因此它可以在多项式时间内运行P问题。这是我能想到的最好的答案。