一类系统优化问题被称为是NP难的，如果有算法可以求解这类问题，也就可以在最多增加多项式时间复杂度的情况下用同样的时间复杂度求解NP类中的任何其他问题。

NP难性属于计算复杂性概念，1971年由加拿大学者S.库克（Stephen Cook）最早提出，通常用来定性刻画某些系统优化问题在计算机上无法有效求解的情形。已知的许多组合优化问题，如TSP问题是NP难问题，0-1背包问题和布尔表达式可满足问题也是NP难问题。在计算复杂性领域中的一个著名的问题是NP类问题是否有多项式求解算法。普遍认为NP类问题不都存在多项式算法。

证明某类优化问题具有NP难性，通常采用将该问题在多项式时间内归约为已知的NP难问题。在系统优化问题中，有些问题已经被证明是NP难的。如有限时间的部分可观马尔可夫决策过程和分布式马尔可夫决策过程都被证明是NP难的。

在这类问题中还没有一个找到有效算法，因此规模较大的NP难问题难以在短时间内精确求解，必须寻求这类问题的有效近似算法。