Algorithm design patterns.
 Greedy.
 Divideandconquer.
 Dynamic programming.
 Maxflow mincut.
 Reductions.
Algorithm design antipatterns.
 NPcompleteness.
 PSPACEcompleteness.
 Undecidability.
PolynomialTime Reductions
 Definition: > Problem X polynomialtime reduces to problem Y if arbitrary instances of problem X can be solved using: > 1. Polynomial number of standard computational steps, plus > 2. Polynomial number of calls to oracle that solves problem Y.
 Notation: X≤_{p}Y
 Design algorithms. If X≤_{p}Y and Y can be solved in polynomialtime, then X can also be solved in polynomial time.
 Establish intractability. If X≤_{p}Y and X cannot be solved in polynomialtime, then Y cannot be solved in polynomial time.
 Establish equivalence. If X≤_{p}Y and Y≤_{p}X, we use notation X≡_{p}Y. In this case, X can be solved in polynomial time iff Y can be.
1. Reduction by Simple Equivalence
 Independent Set: 两两互不相邻的顶点构成的集合

Given a graph G = (V, E) and an integer k, is there a subset of vertices S ⊆ V such that S ≥ k, and for each edge at most one of its endpoints is in S?

 Vertex Cover: 一个集合，使得每条边至少有一个点在集合中

Given a graph G = (V, E) and an integer k, is there a subset of vertices S ⊆ V such that S ≤ k, and for each edge, at least one of its endpoints is in S?

 互为补集，可相互归约. VERTEXCOVER =_{p} INDEPENDENTSET
 Pf. S is an independent set iff V – S is a vertex cover.
 =>
 Let S be any independent set.
 Consider an arbitrary edge (u,v).
 S independent => u ∉ S or v ∉ S => u ∈ V − S or v ∈ V − S.
 Thus, VS covers (u,v).
 <=
 Let VS be any vertex cover.
 Consider two nodes u ∈ S and v ∈ S.
 Observe that (u,v) ∉ E since VS is a vertex cover.
 Thus, no two nodes in S are joined by an edge => S is independent set.
 =>
2. Reduction from Special Case to General Case
 Set Cover Given a set U of elements, a collection S_{1}, S_{2},… ,S_{m} of subsets of U, and an integer k, does there exist a collection of ≤ k of these sets whose union is equal to U?
 VERTEXCOVER ≤_{p} SETCOVER
 Pf. Given a VERTEXCOVER instance G = (V, E), k, we construct a set cover instance (U,S) whose size equals the size of the vertex cover instance.
 Construction
 Create SETCOVER instance:
 k=k, U=E, S_{v} = {e ∈ E: e incident to v}
 Setcover of size ≤ k iff vertex cover of size ≤ k.
 Create SETCOVER instance:
3. Reductions via “Gadgets”
 Literal A boolean variable or its negation.
 x_{i} or $\overline{x_i}$
 Clause A disjunction of literals.
 $C_j = x_1 \vee \overline{x_2} \vee x_3$
 Conjunctive Normal Form 合取范式 A propositional formula Φ that is the conjunction of clauses.
 Φ = C_{1} ∧ C_{2} ∧ C_{3} ∧ C_{4}
 SAT Given CNF formula Φ, does i have a satisfyling truth assignment?
 3SAT SAT where each clause contains exactly 3 literals.
3SAT ≤_{p} INDEPENDENTSET
Pf. Given an instance Φ of 3SAT , we construct an instance (G, k) of INDEPENDENTSET that has an independent set of size k iff Φ is satisfiable.
Construction:
 G contains 3 vertices for each clause, one for each literal.
 Connect 3 literals in a clause in a triangle.
 Connect literal to each of its negations.
G contains independent set of size k= Φ  iff Φ is satisfiable.
 Pf. <= Given satisfying assignment, select one true literal from each triangle. This is an independent set of size k.
 Pf. => Let S be independent set of size k.
 S must contain exactly one vertex in each triangle.
 Set these literals to true, and any other variables in a consistent way
 Truth assignment is consistent and all clauses are satisfied.
 Note:
 each triangular has one node to be chose.
 each sat has one true literal to be chose.
 finally we choose k nodes
SelfReducibility
 Decision Problem. 判定问题
 e.g. Does there exist a vertex cover of size ≤ k?
 Optimization Problem. 优化问题
 e.g. Find vertex cover of minimum cardinality.
 Selfreducibility Optimization problem ≤_{p} decision version.
 Justifies our focus on decision problem.
Ex: to find min cardinality vertex cover.
 (Binary) search for cardinality k* of min vertex cover.
 Find a vertex v such that G – {v} has a vertex cover of size ≤ k* – 1.
 v must be in a vertex cover of size ≤ k*
 Prove by construction: a vertex cover of G – {v} plus v must be a vertex cover of G
 Include v in the vertex cover.
 Recursively find a min vertex cover in G – {v}.
Definitions
P. Decision problems for which there is a polytime algorithm?
NP. 存在多项式时间的验证算法，返回yes
– NP stand for nondeterministic polynomialtime.
EXP. 存在指数级时间算法的决策问题. (指上界，若是多项式时间算法，亦属于EXP)
NPComplete 一个属于NP的问题，所有NP中的其他问题都能归约到这个问题
coNP NP的补集，对一个否定实例，存在一个简洁的验证算法
Asymmetry of NP 去证明一个实例的错误的（NP为证明一个实例是正确的）
NPhard A problem such that every problem in NP reduces to it.
Certifiers and Certificates
Certification algorithm intuition.
 Certifier views things from “managerial” viewpoint.
 Certifier doesn’t determine whether s ∈ X on its own; rather, it checks a proposed proof t that s ∈ X.
Def. Algorithm C(s, t) is a certifier for problem X if for every string s, s ∈ X iff there exists a string t such that C(s, t) = yes.
 where string t is the “certificate” or “witness”
Examples. 1. COMPOSITES. Given an integer s, is s composite? 是否为合数？
1 2 3 4 5 6 7 8 
boolean C(s, t) { if (t <= 1 or t >= s) return false else if (s is a multiple of t) return true else return false } 
 3SAT
 Hamiltonian Cycle 一笔画问题
Check that the permutation contains each node in V exactly once, and that there is an edge between each pair of adjacent nodes in the permutation.
Claim. P ⊆ NP
Pf. Consider any problem X in P
 By definition, there exists a polytime algorithm A(s) that solves X.
 Certificate: t = ϵ, certifier C(s, t) = A(s).
Claim. NP ⊆ EXP
Pf. Consider any problem X in NP
 By definition, there exists a polytime certifier C(s, t) for X.
 To solve input s, run C(s, t) on all strings t with t ≤ p(s).
 Return yes , if C(s, t) returns yes for any of these.
NPCompleteness
Def. Problem X polynomial reduces (Cook) to problem Y if arbitrary instances of problem X can be solved using:
 Polynomial number of standard computational steps, plus
 Polynomial number of calls to oracle that solves problem Y.
Def. Problem X polynomial transforms (Karp) to problem Y if given any input x to X, we can construct an input y in polytime such that x is a yes instance of X iff y is a yes instance of Y.
 多项式时间构造Y的输入，再调用Y的算法
 We blur the distinction of these two conscepts.
Theorem. Suppose Y is an NPcomplete problem. Then Y is solvable in polytime iff P = NP.
Pf. <= If P = NP then Y can be solved in polytime since Y is in NP.
Pf. => Suppose Y can be solved in polytime.
 Let X be any problem in NP. Since X ⊆ p Y, we can solve X in polytime. This implies NP ⊆ P.
 We already know P ⊆ NP. Thus P = NP.