搜索
NPC问题一、SAT、3SAT问题描述二、证明顶点覆盖规约到独立集、团问题一、问题描述二、证明3SAT规约到独立集一、问题描述二、证明3SAT规约到三维匹配一、问题描述二、证明3维匹配规约到三元集合恰当覆盖由于这个规约比较容易，过程略，直接写结果。3DM(X,Y,Z,T){X3C(X∪Y∪Z,T)}3SAT规约到MAX2SAT顶点覆盖规约到无向汉密尔顿回路一、问题描述二、证明三维匹配规约到子集和问题子集和问题规约到划分问题顶点覆盖规约到集合覆盖汉密尔顿回路问题规约到旅行商问题团问题规约到子图同构问题[java]viewplaincopy1.Clique(G=(V,E),k)2.{3.foreachsubgraphG'inGand|V'|=k4.{5.子图同构(G,G')6.}7.}汉密尔顿路径规约到有界度生成树问题[java]viewplaincopy1.Hamilton_Path(G=(V,E))2.{3.有界度生成树(G,1)4.}划分问题规约到背包问题证明电路可满足性问题是NPC问题给定一个输入位数固定为n、且返回yes/no的算法，都能够在多项式时间内转换为一个多项式大小的电路。CIRCUIT-SAT规约到SAT有向汉密尔顿回路规约到无向汉密尔顿回路3SAT规约到有向汉密尔顿回路