Found in articles
NP完全或NP完备 （NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中，決定性問題的等級之一。NP完备是NP与NP困难問題的交集，是NP中最難的決定性問題，所有NP問題都可以在多項式時間內被歸約（reduce to）為NP完備問題。倘若任何NP
problem）。利用这种地雷布局作为证明证据，就证明了该问题属于NP类。 不过，如果一个扫雷局面已经保证自洽（数字、标记和未知方格之间没有矛盾），那么判断其是否有解的问题目前虽未被证明为NP完全，但已被证明为co-NP完全（英语：co-NP-complete）。在这种情况下，扫雷还表现出类似于k-SAT的相变
複雜度類
Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. NP-complete（NPC問題是解決某些數學難題的重要關鍵，這問題暗示人們是否可以將某些演算法的執行效率提升到可接受的範圍）問題的標準指南。
稀疏語言
在1979年，Fortune 證明若任何稀疏語言是co-NP-完全，則P = NP； Mahaney在1982年利用這個證明了如果任何稀疏語言是NP-完全, 則 P = NP (這就是Mahaney's theorem). 在1991年，
certificate）是對一個數是否為質數的簡短證明，它以一種實用的方式證明質數是可以有效驗證的，將質數檢定問題歸入複雜度類NP，並首次有力地證明該問題並非共NP-完備（英语：co-NP-complete）。1970年代初，普拉特與史丹佛大學教授高德納共同設計了KMP演算法，該演算法是詹姆斯·H·莫里斯獨立設計的