【ADS】NP Completeness

Definition

P问题是指：用确定图灵机可以在多项式时间内解决的问题。一个问题可以找到一个能在多项式的时间里解决它的算法。也就是复杂度为O(1),O(log(n)),O(n^a)等的。
NP问题：用非确定图灵机可以在多项式时间内解决。可以在多项式的时间里验证一个解的问题（注意，NP问题不是非P问题！！！）。所以比如最短路问题、TSP旅行商问题，一个解出来了（一条路径出来了），那么我验证这个解（计算这条路径的长度）可以在O(n)的复杂度里解决，所以是NP问题。
NPC（NP Complete，NP完全）问题满足：首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。证明一个问题是NPC问题也很简单。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它（由约化的传递性）。第一个NPC问题是逻辑电路问题（给定一个逻辑电路，问是否存在一种输入使输出为True），并且可以证明所有NP问题都能约化到它（证明过程复杂）。Hamilton 回路、TSP问题、SAT问题（判断一组给定的布林函数，是否可以找到一组变数赋值能使其为真）是NPC问题。
NP Hard问题满足NPC问题定义的第二条但不一定要满足第一条（即所有NP问题都可以约化到它，但它不一定是NP问题），所以NP Hard问题包含了NPC问题。
若A为NP-Hard，A可以规约到B，则B为NP-Hard

所以P问题一定是NP问题，NPC问题也一定是NP问题，NPC问题也一定是NP Hard问题，但NP Hard问题不一定是NP问题。

$L \in P \Rightarrow \bar L \in P$
$L \in NP \Rightarrow \bar L \in co$-$NP$