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

CIRCUIT-SAT. Given a combinational circuit built out of AND, OR, and NOT gates, is there a way to set the circuit inputs so that the output is 1?
Theorem CIRCUIT-SAT is NP-complete.

## Establishing NP-Completeness

Recipe to establish NP-completeness of problem Y.
– Step 1. Show that Y is in NP. – Step 2. Choose an NP-complete problem X. – Step 3. Prove that X p Y.

3-SAT is NP-Complete
Circuit-SAT 的输入构造 3-SAT 的输入:

• Step 1. 对于每个节点i，构造bool变量xi
• Step 2. Make circuit compute correct values at each node.
• x2 = ¬x3 => add x2 ∨ x3, $\overline{x_2}\vee \overline{x_3}$
• x1 = x4 ∨ x5 => add $x_1 \vee \overline{x_4}$, $x_1 \vee \overline{x_5}$, $\overline{x_1}\vee x_4 \vee x_5$
• x0 = x1 ∧ x2 => add $\overline{x_0}\vee x_1$, $\overline{x_0}\vee x_2$, $x_0 \vee \overline{x_1}\vee \overline{x_2}$
• Step 3. Hard-coded input values and output value
• x5 = 0 => add $\overline{x_5}$
• Final step.Turn clauses of length < 3 into clauses of length exactly 3.
• TODO

Lemma Φ is satisfiable iff. the inputs of K can be set s.t. it outputs 1.
Pf. <=

• Suppose there are inputs of K s.t. it outputs 1.
• Compute the values of all the nodes in K.
• According to our construction, this set of values satisfies Φ.

Pf. =>

• Suppose Φ is satisfiable.
• The variable assignment of Φ specifies the values of all the nodes in K.
• Our construction ensures that all the nodes in K are correctly computed and the output is 1.

Six basic genres of NP-complete problems and paradigmatic examples.

• Packing problems: SET-PACKING , INDEPENDENT SET.
• Covering problems: S ET-COVER , VERTEX-COVER.
• Constraint satisfaction problems: SAT , 3-SAT.
• Sequencing problems: HAMILTONIAN-CYCLE , TSP.
• Partitioning problems: 3D-MATCHING, 3-COLOR.
• Numerical problems: SUBSET-SUM , KNAPSACK.

## co-NP

Theorem If NP co-NP, then P NP.
Pf:

• P is closed under complementation.
• If P = NP, then NP is closed under complementation.
• In other words, NP = co-NP.
• This is the contrapositive of the theorem.

Observation. P ⊆ NP ∩ co − NP
PRIMES is in NP ∩ co − NP
FACTOR is in NP ∩ co − NP

## Sequencing Problems

### Hamiltonian Cycle 哈密顿回路

DIR-HAM-CYCLE: given a digraph G = (V, E), does there exists a simple directed cycle Γ that contains every node in V?
Claim. DIR-HAM-CYCLE p HAM-CYCLE
Pf. Given a directed graph G = (V, E), construct an undirected graph G’ with 3n nodes

Claim. G has a Hamiltonian cycle iff G’ does.
Pf. =>

• Suppose G has a directed Hamiltonian cycle Γ.
• Then G’ has an undirected Hamiltonian cycle (same order).

Pf. <=

• Suppose G’ has an undirected Hamiltonian cycle Γ.
• Γ must visit nodes in G’ using one of following two orders:
• …, B, G, R, B, G, R, B, G, R, B, …
• …, B, R, G, B, R, G, B, R, G, B, …
• Blue nodes in Γ make up directed Hamiltonian cycle Γ in G, or reverse of one.

Claim. 3-SAT p DIR-HAM-CYCLE.
Pf. Given an instance Φ of 3-SAT , we construct an instance of DIR-HAM-CYCLE that has a Hamiltonian cycle iff Φ is satisfiable.
Contruction. Given 3-SAT instance Φ with n variables xi and k clauses.

• Construct G to have 2n Hamiltonian cycles.
• Intuition: traverse path i from left to right <=> set variable xi = 1.
• For each clause: add a node and 6 edges.

Claim. Φ is satisfiable iff G has a Hamiltonian cycle.
Pf. =>

• Suppose 3-SAT instance has satisfying assignment x*.
• Then, define Hamiltonian cycle in G as follows:
• if x*i = 1, traverse row i from left to right
• if x*i = 0, traverse row i from right to left
• for each clause Cj, there will be at least one row i in which we are going in “correct” direction to splice node Cj into tour

Pf. <=

• Suppose G has a Hamiltonian cycle Γ.
• If Γ enters clause node Cj, it must depart on mate edge.
• thus, nodes immediately before and after Cj are connected by an edge e in G
• removing Cj from cycle, and replacing it with edge e yields Hamiltonian cycle on G – { C j }
• Continuing in this way, we are left with Hamiltonian cycle Γ in G – { C1, C2, …, Ck }.
• Set x*i = 1 iff Γ traverses row i left to right.
• Since Γ visits each clause node Cj, at least one of the paths is traversed in “correct” direction, and each clause is satisfied.

### Traveling Salesperson Problem

TSP . Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length D?
Claim. HAM-CYCLE p TSP.
Pf.

• Given instance G=(V,E) of HAM-CYCLE, create n cities with distance function
• d(u,v)=1, if (u,v) E
• d(u,v)=2, if (u,v) E
• TSP instance has tour of length n iff G is Hamiltonian.

### Longest Path

• SHORTEST-PATH. Given a digraph G = (V, E), does there exists a simple path of length at most k edges?
• LONGEST-PATH. Given a digraph G = (V, E), does there exists a simple path of length at least k edges?

Claim. 3-SAT p LONGEST-PATH
Pf 1. Redo proof for DIR-HAM-CYCLE , ignoring back-edge from t to s.

Pf 2. Show DIR-HAM-CYCLE p LONGEST-PATH.

• Given an instance of DIR-HAM-CYCLE, split an arbitrary node v of the digraph into two nodes v’ and v”; connect all the incoming edges to v’ and all the outgoing edges to v”.