性最高的一種集合，是計算複雜性理論中最重要的一個概念.設L為一個語言，如果對任何L,ENP,皆有多項式可計算函式f，使
b二(二E L]HJ(二)EL>(即L,是多項式時間多一可化歸到L,L1鎮}, L，則稱L是NP難的.特別地，若L E NP，且L又是NP難的，則稱L是NP完全的.由於當L 1鎮}, L時，可以認為L比L，更難解，因此，NP完全的語言是NP最難的.正因為如此，只要能證明某個 NP完全集是多項式時間可計算的，那么必有P=NP.反之，若能證明某個語言1.，不是多項式時間可計算，但卻是NP的，即1., E NP\P，則NP完全的語言L必定滿足L E NP\P.對NP完全集的研究與P=? NP問題密切相關，這正是它的魅力所在.
第一個NP完全集的例子是庫克(Cook , S. A. >於1971年給出的可滿足性問題的集SAT.卡普(Karp , R. M.)於1972年給出了NP完全性這一術語的明確表述及其嚴格的形式定義，並給出了21個NP完全的問題.此後，越來越多的NP完全集被發現，而且它們涉及數學的幾乎每一個分支.NP類包含大量出現在工業和商業界的實際問題.又由於一般地相信P}NP，因而，一個問題是NP完全的，常可看成它不是P中的一個“證明”，這樣一來，NP完全性又相當於給出了該問題的一個複雜性下界.
b二(二E L]HJ(二)EL>(即L,是多項式時間多一可化歸到L,L1鎮}, L，則稱L是NP難的.特別地，若L E NP，且L又是NP難的，則稱L是NP完全的.由於當L 1鎮}, L時，可以認為L比L，更難解，因此，NP完全的語言是NP最難的.正因為如此，只要能證明某個 NP完全集是多項式時間可計算的，那么必有P=NP.反之，若能證明某個語言1.，不是多項式時間可計算，但卻是NP的，即1., E NP\P，則NP完全的語言L必定滿足L E NP\P.對NP完全集的研究與P=? NP問題密切相關，這正是它的魅力所在.
第一個NP完全集的例子是庫克(Cook , S. A. >於1971年給出的可滿足性問題的集SAT.卡普(Karp , R. M.)於1972年給出了NP完全性這一術語的明確表述及其嚴格的形式定義，並給出了21個NP完全的問題.此後，越來越多的NP完全集被發現，而且它們涉及數學的幾乎每一個分支.NP類包含大量出現在工業和商業界的實際問題.又由於一般地相信P}NP，因而，一個問題是NP完全的，常可看成它不是P中的一個“證明”，這樣一來，NP完全性又相當於給出了該問題的一個複雜性下界.
