NP完全问题

NP完全或NP完备（NP-Complete，缩写为NP-C或NPC），是计算复杂度理论中，决定性问题的档次之一。NPC问题，是NP（非决定性多项式时间）中最难的决定性问题。因此NP完备问题应该是最不可能被化简为P（多项式时间可决定）的决定性问题的集合。若任何NPC问题得到多项式时间的解法，那此解法就可应用在所有NP问题上。