历史简介
：
计算复杂性理论发展：
- 1971年，史提芬·古克证明了第一个NPC问题——
布尔可满足性问题
；- 1972年，理查德·卡普进一步推进，证明了21个不同的NPC问题。《Reducibility Among Combinatorial Problems》”。
1、 SAT问题(SATISFIABILITY)
判断合取范式（有限个简单析取式的合取）是否可满足）
2、 0-1整数规划(0-1 INTEGER PROGRAMMING)
对整形矩阵C和整形向量d，判断是否存在0-1向量x，s.t. Cx=d.
3、 最大团(CLIQUE)
判断图G中是否存在规模为K的团。
4、 (SET PACKING)
判断集合族中是否存在l个两两不交的集合。
5、 最小点覆盖(NODE COVER)
判断是否存在G中规模≤l的点集覆盖G中所有弧(E)
6、 集合覆盖 (SET COVERING)
判断有限集P的有限子集族是否存在规模不超过l的的覆盖。
7、 反馈节点集(FEEDBACK NOTE SET)
对有向图H和正整数k，问是否存在规模不超过k的V的子集C，s.t.对H中的任一圈，都有C中的点。
8、 反馈弧集(FEEDBACK ARC SET)
对有向图H和正整数k，问是否存在规模不超过k的E的子集C，s.t.对H中的任一圈，都有C中的弧。
9、 有向哈密尔顿回路(DIRECTED HAMILTON CIRCUIT)
判断有向图H有没有无重复遍历所有点的有向回路。
10、无向哈密尔顿回路(UNDIRECTEDHAMILTON CIRCUIT)
判断无向图G有没有无重复遍历所有点的回路。
11、3SAT (SATISFIABILITYWITH AT MOST 3 LITERALS PER CLAUSE)
析取式：D1~Dr 文字集：u1~um及其非。
12、图着色数(CHROMATICNUMBER)
对图G，判断是否存在k染色，使相邻节点颜色相异。
13、分团覆盖(LIQUE NUMBER)
判断图G是否可分称不多于k个团。
14、恰好覆盖(EXACT COVER)
判断是否存在子集族的一个子集是全集的分割。
15、(HITTING SET)
对U的子集族S，是否存在U的子集W，使得W与S中的每个集合的交集规模均为1.
16、斯坦纳树(STEINER TREE)
对图G，V的子集R。w为G中的边的权重。求一个G的子树，包含R中所有点，且总权重不超过k。
17、三维匹配 (3-DIMENSIONALMATCHING)
判断T×T×T的子集U是否存在规模为|T|的子集W，其中元素在三个维度上的投影均不相同。
18、0-1背包 (KNAPSACK)
判断对r+1元整数组a1~ar,b，是否存在0-1量xi，s.t.∑ajxj=b。
19、工作规划(JOB SEQUENCING)
有p个工作，每个工作有它要做的时间、ddl、和迟到惩罚三个参数，判断是否存在顺序使得总惩罚不超过K。
20、(PARTITION)
判断s个正整数组成的集合是否可以分成和相等的两部分。
21、最大割(MAX CUT)
给定图G，权重函数w：EàZ.判断是否有不小于W的割。
参考文献：
[1].
Karp的21个NPC问题及其规约
[2].
Karp的21个NP完全问题
[3].
Reducibility among Combinatorial Problems问题之间的规约证