算法的衡量：多项式时间就是高效的，指数时间就是低效的
五子棋有先下策略
重点：
规约：把一个问题X转化成另外一个问题Y的实例，再把通过Y得到的结论转化成X的结论。 X ≤p Y 或者 X→ Y
注意：只能把简单的问题规约到复杂的问题？这里不要纠结所谓的简单复杂，而是应该看规约的定义是什么。
规约：如果X问题的任意的一个实例可以通过多项式时间转化成Y问题的实例，假设Y问题已经有了已知算法Oracle，求得一个解，之后再在多项式时间内把解转化回X问题的解，这样我们就说 X问题可以规约成Y问题。
X（未知）≤ Y (已知）,知道Y算法的复杂度， X的复杂度一定小于等于Y？如果转化的复杂度比Y的复杂度度要高呢？
X（已知）≤ Y(未知），已知X算法没有多项式时间的算法，就推出更复杂的Y算法没有多项式时间算法。
考试重点！
Vertex Cover. Given a graph G = (V , E ) and an integer k , is there a subset of k (or fewer) vertices such that each edge is incident to at least one vertex in the subset?
一个图里面的K个顶点组成一个集合，使得每条边都至少连到一个集合中的点。
Independent Set. Given a graph G = (V , E ) and an integer k , is there a subset of k (or more) vertices such that no two are adjacent?
独立集： 一个图里面的集合， 这些点没有两个是相邻的。