NP困难

描述P, NP, NP完全, 以及NP难之间关系的欧拉图

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

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