关于P的一些澄清
Q1>所有NP问题的多项式时间都可以缩减为NP-COMPLETE问题。
那么所有NP-COMPLETE问题的多项式时间都可以归约为NP问题吗？
Q2>所有NP-COMPLETE问题和NP问题都是多项式时间减少到NP-HARD问题。
那么所有NP-HARD问题的多项式时间都可以缩减为NP / NP-COMPLETE问题吗？
Q3> NP-HARD问题不需要在NP中，那么为什么NP-Hard定义在NP上？
编辑：
不是np-vs-np-complete-vs-np-hard-what-do-it-all-mean的副本：
我在这里问别的东西 - 比如单向还是双向减少？ 我关于NP-Hard的第一个问题正在建立在那里已经讨论过的内容上。
不，减排是单向的，而不是双向的。 如果您可以使用问题B的解决方案解决问题A，这并不总是意味着您可以使用问题A的解决方案解决问题B.
你的第一个问题很好地说明了这一点，
Q1。 那么所有NP-COMPLETE问题的多项式时间都可以归约为NP问题吗？
绝对不会，除非P = NP。 请注意，即使P问题是NP（您不需要任何证书来检查P问题的答案），但是除非P = NP，否则不能将NP完全问题简化为P问题（如果NP完全问题减少到P问题，这立即意味着P = NP）。
请注意，除非P = NP，否则它全都是站立的。 如果证明P = NP，那么很容易看出任何NP问题都可以归结为任何其他NP问题。
顺便说一句，当你说“...可以简化为NP问题的多项式时间”时，你的问题就不太清楚了 。 你的意思是任何 NP问题或至少一个 NP问题？ 如果你的意思是任何 ，我的回答如上。 如果你的意思是“所有NP-COMPLETE问题的多项式时间可以减少到至少一个 NP问题？”，那么答案是肯定的，每一个问题都可以归结为它自己。
链接地址: http://www.djcxy.com/p/39937.html上一篇: Some clarification regarding P
下一篇: Complete VS NP