NP-hard（NP-困难）：在计算复杂性理论中，指一类问题至少和 NP 类中最难的问题一样难；如果能在多项式时间内解决某个 NP-hard 问题，就能在多项式时间内解决所有 NP 问题。（注：NP-hard 问题不一定属于 NP，也不一定是判定问题。）
/ˌɛnˌpiː ˈhɑːrd/
This scheduling problem is NP-hard.
这个排班问题是 NP-困难的。
Even with clever heuristics, finding the exact optimum for this NP-hard optimization problem may be impractical on large inputs.
即使用上巧妙的启发式方法，在大规模输入上精确求解这个 NP-困难的优化问题也可能并不现实。
NP-hard 来自 NP（nondeterministic polynomial time，非确定性多项式时间）与 hard（困难的）组合而成，强调“难度至少达到 NP 中最难问题的水平”。该术语在计算复杂性研究中用于描述“可归约难度”的上界性质：许多已知难题都能在多项式时间内归约到 NP-hard 问题上。
Select Language