【原创】如何证明一个问题是否NP？ [ 香山居士 ] 于:2004-01-17 07:53:34 主题帖

回答啊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的简写，标准翻译应该是“非决定性多项式”，而不是“非多项式”。