Analysis of Algorithms
V. Adamchik CSCI 570 Lecture 12 University of Southern California
NP-Completeness – II
Reading: chapter 9
In 1936 Alan Turing described
• A simple formal model of computation now known as Turing machines.
• A proof that TM can NOT solve the halting problem.
• A universal TM that can simulate any TM.
• A proof that NO Turing machine can determine whether a given proposition is provable from the axioms of first- order logic.
• Compelling arguments that a problem not computable by a Turing machine is not “computable” in the absolute (human) sense.
• A non-deterministic Turing machine: for each state it makes an arbitrary choice between a finite of possible transitions.
Deterministic Turing Machine
transition
The machine that takes a binary string and appends 0 to the left side of the string.
states
start
0,0,R
1,1,R
Input: #10010Δ Output: #010010Δ
# – leftmost char Δ – rightmost char
Transition on each edge read,write,move (L or R)
S0
1,0,R 0,1,R
S1
accept
reject
Non-Deterministic Turing Machine
• NDTM is a choice machine: for each state it makes an arbitrary choice between a finite (possibly zero) number of states.
• The computation of a NDTM is a tree of possible configuration paths.
• One way to visualize NDTM is that it makes an exact copy of itself for each available transition, and each machine continues the computation.
• Rabin & Scott in 1959 shown that adding non-determinism does not result in more powerful machine.
• For any NDTM, there is a DTM that accepts and rejects exactly the same strings as NDTM.
• P vs. NP is about whether we can simulate NDTM in polynomial time.
Complexity Classes
P = set of problems that can be solved in polynomial
time by a DTM.
NP = set of problems that can be solved in polynomial time by a NDTM.
NP = set of problems for which solution can be verified in polynomial time by a deterministic TM.
X is NP-Hard, if ∀Y ∈ NP and Y ≤p X.
X is NP-Complete,
if X is NP-Hard and X NP.
Venn Diagram (P ≠ NP)
NPC problems are the most difficult NP problems.
NP-hard
NP-complete
NP
Undecidable: Halting Problem
optimization & decision problems
only decision problems
P
It’s not known if NPC problems can be solved by a
deterministic TM in polynomial time.
NPC problems can be solved by a non-deterministic TM in polynomial time.
NP-Completeness Proof Method
To show that X is NP-Complete:
1) Show that X is in NP
2) Pick a problem Y, known to be an NP-Complete 3) Prove Y ≤p X (reduce Y to X)
Transf.
Algorithm for X
Algorithm for Y YX
yes no
Cook-Levin Theorem (1971) Theorem. CNF SAT is NP-complete.
The theorem was proven without means of reduction
NP-Complete Problems
Independent Set:
Given graph G and a number k, does G contain
a set of at least k independent vertices?
Vertex Cover:
Given a graph G and a number k, does G
contain a vertex cover of size at most k.
A Hamiltonian cycle:
Given a graph G, does G contain a cycle that visits each vertex exactly once.
Discussion Problem 1
Given SAT in Conjunctive Normal Form (CNF) (X1∨¬X3)∧(X1 ∨¬X2∨X4∨X5)∧…
with any number of clauses and any number of literals in each clause. Prove that SAT is polynomial time reducible to 3SAT.
Discussion Problem 2
You are given an undirected graph G = (V, E) and for each vertex v, you are given a number p(v) that denotes the number of pebbles placed on v. We will now play a game where the following move is the only move allowed. You can pick a vertex u that contains at least two pebbles, and remove two pebbles from u and add one pebble to an adjacent vertex. The objective of the game is to perform a sequence of moves such that we are left with exactly one pebble in the whole graph. Show that the problem of deciding if we can reach the objective is NP-complete. Reduce from the Hamiltonian Path problem.
Graph Coloring
Given a graph, can you color the nodes with ≤ k colors such that the endpoints of every edge are colored differently?
Theorem. (k>2)
k-Coloring is NP-complete.
Graph Coloring: k = 2
How can we test if a graph has a 2-coloring?
3-SAT ≤p 3-colorable
We construct a graph G that will be 3-colorable iff the 3- SAT instance is satisfiable.
Graph G consists of the following gadgets.
A truth gadget:
TF
A gadget for each variable:
a ¬a
3-SAT ≤p 3-colorable
Combining those gadgets together (for three literals)
3-SAT ≤p 3-colorable
A special gadget for each clause
This gadget connects a truth gadget with variable gadgets.
a
b
c
T
3-SAT ≤p 3-colorable
Suppose all a, b and c are all False (red).
T
3-SAT ≤p 3-colorable
We have showed that if all the variables in a clause are false, the gadget cannot be 3-colored.
Example: a ∨ ¬b ∨ c
Example with four clauses
a=c=T b=d=F
3-SAT ≤p 3-colorable Claim: 3-SAT instance is satisfiable if and only if
G is 3-colorable.
Proof: ⇒)
3-SAT ≤p 3-colorable Claim: 3-SAT instance is satisfiable if and only if
G is 3-colorable.
Proof: ⇐)
Sudoku: n2×n2
NP-? NP-hard?
Sudoku Graph
Sudoku
Constructing a Sudoku graph we have proved:
Don’t be afraid of NP-hard problems.
Many reasonable instances (of practical interest) of problems in class NP can be solved!
The largest solved TSP an 85,900-vertex route calculated in 2006. The graph corresponds to the design of a customized computer chip created at Bell Laboratories, and the solution exhibits the shortest path for a laser to follow as it sculpts the chip.
Discussion Problem 3
Prove that 4-COLOR is NP-complete.
Discussion Problem 4
The Steiner Tree problem is as follows. Given an undirected weighted graph G=(V,E) with positive edge costs, a subset of vertices R ⊆ V, and a number C. Is there a tree in G that spans all vertices in R (and possibly some other in V) with a total edge cost of at most C? Prove that this problem is NP-complete by reduction from Vertex Cover.
Example. B 12 C R = {A,F,D} and C = 34. 16
20 A497D
13
F
18
4
E
G
B A
F
C
D
E
BC
D
A
F
E
BC
D
A
F
E