找一个三角形，涂上三个不同的颜色，原来的图的每个点都和这三角形的三个点连接， 这样用7color涂上整个图，因为原图的每个点都不能够取三角形的三个颜色，这样就可以变成4color问题。
P. Decision problems for which there exists a poly-time algorithm.（只是回答Yes or No)
NP: set of decision problems for which there exists a poly-time certifier.
给定一个实例，一个解，可以在多项式时间内判定这个解是这个实例的解（可验证）
EXP. Decision problems for which there exists an exponential-time algorithm.
NP-complete. A problem Y ∈ NP with the property that for every problem X∈NP,X≤P Y.
poposittion: Suppose Y ∈ NP-complete. Then, Y ∈ P iff P = NP.
P→ NP : 都已经把解解出来了当然就可以判定了 。 NP→ EXP, 对exp上的每个可能的实例都用NP来判定一下是不是解，一旦是解就说明找到了解。
倾向于认为P ≠ NP
P一定不等于EXP， eg.枚举子集
Fact. p /= EXP⇒eitherp /=NP,orNP /=EXP,orboth.
由于所有的NP问题都可以多项式规约到某一个NP Complete问题，所以只要一个NP Complete问题能在多项式时间内得到解决，那么所有的NP问题都可以在多项式时间内得到结局了。
"Complete" refers to the property of being able to simulate everything in the same complexity class.