Algorithms
Proof of NP-Completeness
M. K. Shan, CS, NCCU 1
Preliminary
n Polynomial time vs. Exponential time
n Problem Complexity
n Universal Computer Model: Turing machine
n Deterministic vs. Non-deterministic Turing Machine
n Optimization Problem vs. Decision Problem
M. K. Shan, CS, NCCU
M. K. Shan, CS, NCCU
Problem Complexity
n P Problem
o problem solved by deterministic algorithm in polynomial time.
o problem solved by deterministic Turing machine in polynomial time.
n NP Problem (Non-deterministic Polynomial)
o problem solved by non-deterministic algorithm in polynomial time
o problem solved by non-deterministic Turing machine in polynomial
time
n NP-Hard
o problem which every NP problem is polynomial reducible to.
n NP-Complete
o problem which is NP and is also NP-Hard
M. K. Shan, CS, NCCU
Proof of
NP Complete Problems
M. K. Shan, CS, NCCU 5
Satisfiability Problem
n Cook’s theorem
o The satisfiability problem is NP-complete
o NP=P iff the satisfiability problem is a P problem
n Boolean formula
o literal: x1, ~x1
o clause: (~x1 v x2)
o formula: conjunctive normal form, (~x1 v x2) ^ x1 ^ x3
o Every Boolean formula can be transformed into CNF
o Logical consequence
• e.g. x1=0, x2=1, x3=1, F=(~x1 v x2) ^ x1 ^ x3 = 0
• A formula G is a logical consequence of formula F
iff whenever F is true, G is true
M. K. Shan, CS, NCCU
Satisfiability Problem (cont.)
n A boolean expression is said to be satisfiable
if there exists an assignment of 0s and 1s to its variable
such that the values of the expression is 1.
n SAT
o Given a Boolean formula,
determine whether this formula is satisfiable or not
e.g. F = (~x1 v x2) ^ x1 ^ x3
o the first NP-complete problem ever found
M. K. Shan, CS, NCCU
Proof of NP-Completeness for SAT
n SAT is NP-Complete
o SAT is NP
!guess a truth assignment &
check that it satisfies the expression in polynomial time
o SAT is NP-Hard
!Turing machine can be described by a Boolean expression
i.e. expression is satisfiable iff the Turing machine will
terminate for the given input.
\ Any NP problem can be described by an instance of a SAT
M. K. Shan, CS, NCCU
Proof of NP-Complete
n Lemma 11.3
A problem X is an NP-Complete problem
if
(1) X belongs to NP
(2) Y is polynomial reducible to X, for some NP-complete problem Y
NP Y X
NP-Complete
M. K. Shan, CS, NCCU
Clique Problem
n Clique: complete subgraph
* complete: each pair of vertices is adjacent
n Clique problem
o optimization problem:
given an undirected graph G,
find the maximum clique
o decision problem
given an undirected graph G and an integer k,
determine whether G has a clique of size ³ k
w x maximum clique:
{w, x, u, z}
v
{v, w, z}: maximal
y {u, w, z}: not maximal
z u
M. K. Shan, CS, NCCU
Proof of NP-Completeness of
Clique Problem
x’
x y
y y’
z’ z’
z
M. K. Shan, CS, NCCU
Proof of NP-Completeness of Clique Problem (cont.)
(1) If SAT 有解(Satisfiable)，對應的 Graph 就有size ³ m 的 Clique。
如果 SAT 有解，那麼每個 Clause 至少有一個出現的變數是 1。
我們只要在 Graph 中每個 Column 選取這些變數所對應的 Vertices，就會形成 Clique。
(2) If Graph 有 ³ m 的 Clique，對應的 SAT 就有解。
如果 Graph 有 ³ m的 Clique,
那麼每個 Column 都會有一個 Clique 的 Vertex (因為同一個 Column 不會有 Edges)。
我們只要將 CNF 中，這些 Vertex 所對應的變數，Assign 為 True, CNF 就會是 True，
也就是 Satisfiable。(因為互補的變數之間不會有 Edges, 因此不會發生互相矛盾的情形)
x’
x y
y y’
z’ z’
z
Vertex Cover Problem
n Let G=(V, E) be an undirected graph
A vertex cover C of G
= a set of vertices C such that " edge in G is incident to at least one
of vertices in C
n Example: {v, u} is a vertex cover
{w, z} is not vertex cover, ! edge <v, u>
{w, v, z} is a vertex cover
{w, v, z, u} is a vertex cover
{v, u} is the minimum vertex cover
v w
z u
M. K. Shan, CS, NCCU
Vertex Cover Problem
n Vertex cover problem
o optimization problem:
given an undirected graph G,
find the minimum vertex cover
o decision problem
given an undirected graph G and an integer k,
determine whether G has a vertex cover containing £ k vertices
• e.g. whether G has a vertex cover containing £ 3 vertices
Yes, {w, v, x}, {v, u}
v w
z u
M. K. Shan, CS, NCCU
Proof of NP-Completeness of
Vertex Cover Problem
n vertex cover is NP
!guess a cover of size <= k &
check it in polynomial time
n vertex cover is NP-hard
o reduce clique to vertex cover in polynomial time
o construct a complement graph G’=(V, E’)
o if G has a clique of size k, G’ has a vertex cover of size n-k
o if G’ has a vertex cover k, G has a clique of size n-k
G = (V, E) G’ = (V, E’)
a c e a c e
g g
b d f b d f
More NP-Complete Problems
n Hamiltonian cycle
o a simple cycle that contains each vertex exactly once
o determine whether a given graph contains a Hamiltonian cycle
n Traveling salesman
o traveling salesman tour is a Hamiltonian cycle in a weighted
complete graph
o shortest path of traveling tour
n Hamiltonian path
n Independent set
n 3-dimensional matching
n Partition: partition into two subsets with the same size
n Knapsack
n Bin packing M. K. Shan, CS, NCCU
Traveling Salesman Problem
n Given a weighted directed graph, to determine a tour
with minimum total weight on its edges
o tour: a path that starts at one vertex, ends at that vertex &
visits all the other vertices exactly once.
M. K. Shan, CS, NCCU
Techniques to Deal with
NP-Complete Problems
M. K. Shan, CS, NCCU 18
Techniques for Dealing with
NP-complete Problems
n It seems that NP-complete problem cannot be solved precisely &
completely with polynomial time algorithm
n Techniques to deal with NP-complete problem
o approximation algorithm: not lead to optimal (precise) solution
o allow algorithm for some special inputs
• e.g. vertex cover is NP-complete, but can be solved in
polynomial time for bipartite graphs.
o algorithms whose running time is exponential, but work well
for small inputs
• Backtracking
• Branch and bound
M. K. Shan, CS, NCCU
Branch and Bound
n Solution space represented as a tree for multi-stage shortest path
problem
a
1 2
3
b 5 e b c d
1 3 4 4
3 1 5 3 4 3 2 7
a c f h e g e f f g
3
2 1
2
d 7 g 4 1 4 1 1 1
h h h h h h
Shortest path?
10 5 11 7 5 10
Tree representation of Solution space
M. K. Shan, CS, NCCU
Branch and Bound
n bound the search space to avoid exhaustive searching solution
space
1 2 1 2
3 3
b c d b c d
5 3 4 3 2 7 5 3 4 3 2 7
e g e f f g e g e f f g
>6 >7 >6 >9
4 1 4 1 1 1 1 1
h h h h h h h h
10 5 11 7 5 10 5 5
M. K. Shan, CS, NCCU
Applications of
NP-Complete Problems
M. K. Shan, CS, NCCU 22
Application of NP-Completeness
n Security
o沒有永遠無法破解的密碼，但有要花很多時間才能破解的密碼
o 很多時間才能破解 Þ 破解需exponential time
o RSA利用質因數分解是NP-complete的特性
n Public key system
Public key (n, e)
加密 message
c1=F(n,e,m1) m1
c1
解密
Secret key (n, d)
m1=G(n,d,c1)
m1
c2
解密 加密 message
m2=G(n,d,c2) c2=F(n,e,m2) m2
m2 Public key (n, e)
M. K. Shan, CS, NCCU
RSA
n Invented by Rivest, Shamir, & Adleman at MIT in 1978
o choose two prime number, p, q
o compute n=p*q, z=(p-1)*(q-1)
o choose a number d relative prime(互質) to z
o find e such that (e*d) mod z =1
o 加密 , given message m, cipher message c=me mod n
o 解密, given cipher message c, decipher message m=cd mod n
o n & e公開，但是d不公開，解密需要知道d, 由n倒求出d需要exponential time
（因為質因數分解是NP-complete）
n Example
o choose two prime number, 5, 7
o compute n=5*7=35, z=(5-1)*(7-1)=24
o choose a number d =11 relative prime(互質) to 24
o find e=11 such that (e*d) mod z =1
o 加密 , given message m=2, cipher message c=211 mod 35= 18
o 解密, given cipher message c, decipher message m=1811 mod 35 = 2
M. K. Shan, CS, NCCU
Conclusions
n Problem difficulty
n Computer Model: Turing Machine
o Non-deterministic Turing Machine
n Problem
o optimization problem
o decision problem
n Deterministic vs. Non-deterministic Algorithm
n P, NP, NP-Hard, NP-Complete, Undecisible Problems
n P = NP ?
n Proof of NP-Complete by Reduction
M. K. Shan, CS, NCCU
