NP困难：修订间差异
删除的内容 添加的内容
无编辑摘要 |
无编辑摘要 |
||
| 第5行： | 第5行： | ||
'''NP困难'''（'''NP-hard''',non-deterministic polynomial-time hard）问题是[[计算复杂性理论]]中最重要的复杂性类之一。某个问题被称作NP困难，当所有[[NP]]问题可以在[[多项式时间图灵归约]]到这个问题。 |
'''NP困难'''（'''NP-hard''',non-deterministic polynomial-time hard）问题是[[计算复杂性理论]]中最重要的复杂性类之一。某个问题被称作NP困难，当所有[[NP]]问题可以在[[多项式时间图灵归约]]到这个问题。 |
||
因为NP困难问题未必可以在多项式的时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间内的解 |
因为NP困难问题未必可以在多项式的时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间内的解（若[[P/NP问题#P.3DNP|P=NP]]），NP困难问题依然可能没有多项式时间内的解。因此NP困难问题“至少与NPC问题一样难”。 |
||
{{复杂度类}} |
{{复杂度类}} |
||
2017年6月4日 (日) 04:14的版本
 | 此條目需要擴充。 (2013年3月12日) |
 | 此條目没有列出任何参考或来源。 (2013年3月12日) |
NP困难（NP-hard,non-deterministic polynomial-time hard）问题是计算复杂性理论中最重要的复杂性类之一。某个问题被称作NP困难，当所有NP问题可以在多项式时间图灵归约到这个问题。
因为NP困难问题未必可以在多项式的时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间内的解（若P=NP），NP困难问题依然可能没有多项式时间内的解。因此NP困难问题“至少与NPC问题一样难”。
