NP困难 NP困难NPhardness nondeterministic polynomialtime hardness问题是计算复杂性理论中最重要的复杂性类之一如果所有NP问题都可以多项式时间归约到某个问题则称该问题为NP困难 因为NP困难问题未必可以在多项式时间内验证一个解的正确性即不一定是NP问题因此即使NP完全问题有多项式时间的解PNPNP困难问题依然可能没有多项式时间的解因此NP困难问题至少与NP完全问题一样难