NP困难术语 / 維基百科,自由的 encyclopedia NP困难(NP-hardness, non-deterministic polynomial-time hardness)问题是计算复杂性理论中最重要的复杂性类之一。如果所有NP问题都可以多项式时间归约到某个问题,则称该问题为NP困难。 此條目需要擴充。 (2013年3月12日) 提示:此条目页的主题不是心灵哲学上的困难问题。 描述P, NP, NP完全,以及NP困难之间关系的欧拉图 因为NP困难问题未必可以在多项式时间内验证一个解的正确性(即不一定是NP问题),因此即使NP完全问题有多项式时间的解(P=NP),NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。
NP困难(NP-hardness, non-deterministic polynomial-time hardness)问题是计算复杂性理论中最重要的复杂性类之一。如果所有NP问题都可以多项式时间归约到某个问题,则称该问题为NP困难。 此條目需要擴充。 (2013年3月12日) 提示:此条目页的主题不是心灵哲学上的困难问题。 描述P, NP, NP完全,以及NP困难之间关系的欧拉图 因为NP困难问题未必可以在多项式时间内验证一个解的正确性(即不一定是NP问题),因此即使NP完全问题有多项式时间的解(P=NP),NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。