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

算法设计与分析笔记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变量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”.

Leave a Reply

Your email address will not be published.