# 算法设计与分析笔记0x0C —— Part 1 NP完全

Algorithm design patterns.

• Greedy.
• Divide-and-conquer.
• Dynamic programming.
• Max-flow min-cut.
• Reductions.

Algorithm design anti-patterns.

• NP-completeness.
• PSPACE-completeness.
• Undecidability.

## Polynomial-Time Reductions

• Definition: > Problem X polynomial-time 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: XpY
• Design algorithms. If XpY and Y can be solved in polynomial-time, then X can also be solved in polynomial time.
• Establish intractability. If XpY and X cannot be solved in polynomial-time, then Y cannot be solved in polynomial time.
• Establish equivalence. If XpY and YpX, we use notation XpY. 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?

• 互为补集，可相互归约. VERTEX-COVER =p INDEPENDENT-SET
• 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, V-S covers (u,v).
• <=
• Let V-S be any vertex cover.
• Consider two nodes u ∈ S and v ∈ S.
• Observe that (u,v) E since V-S 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 S1, S2,… ,Sm of subsets of U, and an integer k, does there exist a collection of k of these sets whose union is equal to U?
• VERTEX-COVER p SET-COVER
• Pf. Given a VERTEX-COVER 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 SET-COVER instance:
• k=k, U=E, Sv = {e ∈ E: e incident to v}
• Set-cover of size k iff vertex cover of size k.

• Literal A boolean variable or its negation.
• xi 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.
• Φ = C1 ∧ C2 ∧ C3 ∧ C4
• SAT Given CNF formula Φ, does i have a satisfyling truth assignment?
• 3-SAT SAT where each clause contains exactly 3 literals.

3-SAT p INDEPENDENT-SET
Pf. Given an instance Φ of 3-SAT , we construct an instance (G, k) of INDEPENDENT-SET 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

### Self-Reducibility

• Decision Problem. 判定问题
• e.g. Does there exist a vertex cover of size k?
• Optimization Problem. 优化问题
• e.g. Find vertex cover of minimum cardinality.
• Self-reducibility 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 poly-time algorithm?
NP. 存在多项式时间的验证算法，返回yes
– NP stand for nondeterministic polynomial-time.

EXP. 存在指数级时间算法的决策问题. (指上界，若是多项式时间算法，亦属于EXP)
NP-Complete 一个属于NP的问题，所有NP中的其他问题都能归约到这个问题
co-NP NP的补集，对一个否定实例，存在一个简洁的验证算法
Asymmetry of NP 去证明一个实例的错误的（NP为证明一个实例是正确的）
NP-hard 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. 3-SAT
2. 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 poly-time 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 poly-time 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.

### NP-Completeness

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 poly-time 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 NP-complete problem. Then Y is solvable in poly-time iff P = NP.
Pf. <= If P = NP then Y can be solved in poly-time since Y is in NP.
Pf. => Suppose Y can be solved in poly-time.

• Let X be any problem in NP. Since X p Y, we can solve X in poly-time. This implies NP P.
• We already know P NP. Thus P = NP.