NP困难

维基百科,自由的百科全书
跳转至: 导航搜索
描述P, NP, NP完全, 以及NP难之间关系的欧拉图

NP困难(NP-hard,non-deterministic polynomial-time hard)问题是计算复杂性理论中最重要的复杂性类之一。某个问题被称作NP困难,当且仅当存在一个NP完全问题可以在多项式时间图灵归约到这个问题。

因为NP困难问题未必可以在多项式的时间内验证一个解的正确性(即不一定是NP问题),因此即使NP完全问题有多项式时间内的解,NP困难问题依然可能没有多项式时间内的解。因此NP困难问题“至少与NPC问题一样难”。