证明P <= NP

Question

正如大多数人所知,P = NP是未经证实的,似乎不太可能是真的.证据证明P <= NP且NP <= P.但其中只有一个很难.

P <= NP几乎是定义为真.事实上,这是我知道如何声明P <= NP的唯一方法.这很直观.你怎么证明P <= NP？

Answer 1

NP中的每个问题都由非确定性图灵机[在多项式时间]解决.(按定义*)

P中的每个问题都由确定性图灵机[在多项式时间]求解.(根据定义)

每个确定性图灵机也是不确定性图灵机.(明显)

因此,P中的每个问题都由非确定性图灵机[在多项式时间]解决.

因此,P中的每个问题都是NP中的问题.因此P⊆NP.

*让我们阅读关于NP 的维基百科文章:

在等价的形式定义中,NP是由非确定性图灵机在多项式时间内可解决的一组决策问题.

没有必要将关于多项式验证的这些内容引入到这样一个简单的推理中.

Answer 2

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

引用维基百科:

P [中的所有问题都在NP中](因为,给出P中问题的证书,我们可以忽略证书,只是在多项式时间内解决问题.或者,请注意,确定性图灵机也是一个非确定性的图灵机恰好没有使用任何非决定论.)

它所引用的证书是解的多项式时间验证; 正如你所说,你可以P在多项式时间内解决一个问题,因此你将得到一个已经在多项式时间内得到验证的解决方案NP.

Joey Adams的答案是第二种解释,就(非)确定性图灵机的可解性而言.有关该定义的更多解释,请参阅维基百科文章NP.

我认为你应该注意的是,证明很简单的事实并不意味着它不是证明."按照定义"是一个完全有效的逻辑步骤.