在提出NPC的概念之后，绝大多数“自然”的难题最后都被证明是NPC问题，只有三个例外，它们分别是：

• 线形规划问题；
• 图同构问题；
• 素数判定问题与大数分解问题。