NP-hard 是计算复杂性理论中的一类判定问题，指那些目前不存在已知多项式时间精确算法、只能随规模增长付出指数级或更高代价求解的问题。它与 NP 完全（NP-complete）密切相关：一个 NP-hard 问题未必本身属于 NP，但所有 NP 问题都可在多项式时间内归约到它。TSP（旅行商问题）、图着色、整数规划等经典组合优化问题都属于这一类，因此 NP-hard 不仅是理论概念，也直接影响运筹优化、机器学习和金融建模的实际可行边界。
NP-hard 问题的近期研究进展
当前焦点与观察点
围绕 NP-hard 问题的研究大致呈两条主线。一是理论侧的松弛与近似：通过证明多项式时间算法的存在性（如鲁棒老虎机的学习器）或给出遗憾度、最优性的可认证界，把 NP-hard 的困难性约束在可控误差范围内。二是方法侧的学习驱动求解：进化算法、强化学习等启发式方法被广泛用于基数约束组合优化、图组合优化等场景，争议在于这些方法通常缺乏最优性保证，实际效果依赖具体实例分布。
值得观察的动向包括：可认证最优性与启发式效率能否在大规模推理内存调度等工程问题上兼得；以及针对 NP-hard 底层结构的松弛研究是否会催生新的学习目标设计。在 P 与 NP 关系仍未解决的背景下，多数实践仍在"高效近似 + 问题结构利用"这一框架内推进。