co-NP-complete

NP完全或NP完备 （NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中，決定性問題的等級之一。NP完备是NP与NP困难問題的交集，是NP中最難的決定性問題，所有NP問題都可以在多項式時間內被歸約（reduce to）為NP完備問題。倘若任何NP

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·莫里斯獨立設計的

B Virus: Multiple Cocirculating Lineages and Frequent Reassortment of the NP, M, and NS Genes. J. Virol. 1999, 73 (5): 4413–26. PMC 104222 . PMID 10196339