算法设计与分析笔记0x0D —— (Part 2)NP完全 NP and Computational Intractability

**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变量
*x*_{i} - Step 2. Make circuit compute correct values at each node.
*x*_{2}= ¬*x*_{3}=> add*x*_{2}∨*x*_{3}, $\overline{x_2}\vee \overline{x_3}$*x*_{1}=*x*_{4}∨*x*_{5}=> add $x_1 \vee \overline{x_4}$, $x_1 \vee \overline{x_5}$, $\overline{x_1}\vee x_4 \vee x_5$*x*_{0}=*x*_{1}∧*x*_{2}=> 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
*x*_{5}= 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* ⊆ *N**P* ∩ *c**o* − *N**P*

PRIMES is in *N**P* ∩ *c**o* − *N**P*

FACTOR is in *N**P* ∩ *c**o* − *N**P*

## 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 *x*_{i} and k clauses.

- Construct G to have 2
^{n}Hamiltonian cycles. - Intuition: traverse path i from left to right <=> set variable
*x*_{i}= 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
*C*_{j}, there will be at least one row i in which we are going in “correct” direction to splice node*C*_{j}into tour

- if

Pf. <=

- Suppose G has a Hamiltonian cycle
*Γ*. - If
*Γ*enters clause node*C*_{j}, it must depart on mate edge.- thus, nodes immediately before and after
*C*_{j}are connected by an edge e in G - removing
*C*_{j}from cycle, and replacing it with edge e yields Hamiltonian cycle on G – { C j }

- thus, nodes immediately before and after
- Continuing in this way, we are left with Hamiltonian cycle
*Γ*′ in G – {*C*_{1},*C*_{2}, …,*C*_{k}}. - Set
*x**_{i}= 1 iff*Γ*′ traverses row i left to right. - Since
*Γ*visits each clause node*C*_{j}, 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”.