NP难性（NP-hard），理学-系统科学-系统技术科学-系统控制与运筹-〔系统优化控制〕-优化问题的复杂性，用NP表示不确定多项式时间复杂类，即存在不确定图灵机在多项式时间内求解的判定问题类。一类系统优化问题被称为是NP难的，如果有算法可以求解这类问题，也就可以在最多增加多项式时间复杂度的情况下用同样的时间复杂度求解NP类中的任何其他问题。NP难性属于计算复杂性概念，1971年由加拿大学者S.库克（Stephen Cook）最早提出，通常用来定性刻画某些系统优化问题在计算机上无法有效求解的情形。已知的许多组合优化问题，如TSP问题是NP难问题，0-1背包问题和布尔表达式可满足问题也是NP难问题。在计算复杂性领域中的一个著名的问题是NP类问题是否有多项式求解算法。普遍认为NP类问题不都存在多项式算法。证明某类优化问题具有NP难性，通常采用将该问题在多项式时间内归约为已知的NP难问题。在系统优化问题中，有些问题已经被证明是NP难的。如有限时间的部分可观马尔可夫决策过程和分布式马尔可夫决策过程都被证明是NP难的。