此条目需要扩充. (2013年3月12日)
请协助改善这篇条目,更进一步的信息可能会在讨论页或扩充请求中找到.请在扩充条目后将此模板移除.
提示:此条目的主题不是心灵哲学上的困难问题.
NP困难(NP-hardness non-deterministic polynomial-time hardness)问题是计算复杂性理论中最重要的复杂性类之一.如果所有NP问题都可以多项式时间归约到某个问题,则称该问题为NP困难.
因为NP困难问题未必可以在多项式时间内验证一个解的正确性(即不一定是NP问题),因此即使NP完全问题有多项式时间的解(P=NP),NP困难问题依然可能没有多项式时间的解.因此NP困难问题"至少与NP完全问题一样难".
本页面最后修订于2022年12月9日 (星期五) 17:49.
维基媒体基金会是按美国国内税收法501(c)(3)登记的非营利慈善机构.