五千年(敝帚自珍)

主题:【原创】如何证明一个问题是否NP? -- 香山居士

全看分页树展 · 主题
家园 【原创】如何证明一个问题是否NP?

回答啊4兄的问题。

很显然,不是说我找不到Polynomial的算法,那这个问题就是NP,那只能证明我笨。

标准办法是从一个已知的NP问题推导出这个问题,而这个推导的复杂程度是Polynomial的。

这可以用反证法来证明:

已知问题A是NP问题,而且经过一番推导可以得出问题B,而这个推导是Polynomial的。假设问题B是P,即存在Polynomial(O(n^c))算法可以解决问题B,那么我们就可以先把问题A转化为问题B,再解决问题B。因为这两个步骤都是Polynomial的,也就是说我们发现了Polynomial的算法解决问题A。而这与已知问题A是NP问题矛盾。所以我们的假定是错的,问题B一定也是NP问题。

我们看到了,所有的NP问题好像一条铁链,一环套一环。如果我们对其中一个问题找到了Polynomial的算法,就砍断了这条铁链,解决了所有问题。

但这就牵扯到“第一个”的NP问题的问题。即:我们需要一个已知的NP问题来证明这个问题,那么很显然,第一个NP问题不能用这个方法来证明。第一个NP问题是什么?它是怎么证明的?

对这个问题我没有具体的研究过。我猜第一个NP问题是SAT问题,我知道有人用了一个NP的图灵机解决了这个问题。学计算机的朋友们应该知道,图灵机是现代计算机的基本模型。

最后顺便说一句,NP是Nondeterministic Polynomial的简写,标准翻译应该是“非决定性多项式”,而不是“非多项式”。


本帖一共被 3 帖 引用 (帖内工具实现)
全看分页树展 · 主题


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河