主题:【原创】如何证明一个问题是否NP? -- 香山居士
共:💬1
回答啊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 帖 引用 (帖内工具实现)