Tutorial 8
NP-Complete Problems
Computer Algorithms Design and Analysis
Decision Problem
Statement of a decision problem
Part 1: instance description defining the
input
Part 2: question stating the actual yes-
or-no question
A decision problem is a mapping from all
possible inputs into the set {yes, no}
Computer Algorithms Design and Analysis
The Class P
A polynomially bounded algorithm is one with its
worst-case complexity bounded by a polynomial
function of the input size.
A polynomially bounded problem is one for which
there is a polynomially bounded algorithm.
The class P is the class of decision problems
that are polynomially bounded.
Computer Algorithms Design and Analysis
Nondeterministic Algorithm
Phase 1 Guessing:
generating arbitrarily
void “certificate”, i.e.
voidnondetA(String
nondetA(Stringinput)
input) proposed solution
String
Strings=genCertif();
s=genCertif();
Boolean
BooleanCheckOK=verifyA(input,s);
CheckOK=verifyA(input,s);
ifif(checkOK) The
Thealgorithm
algorithm
(checkOK) may
Output maybehave
behave
Output“yes”;
“yes”; differently
differentlyon
on
return;
return; the
thesame
sameinput
input
in
indifferent
different
executions:
executions:
Phase 2 Verifying: determining if s is a “yes”
“yes”oror“no
“no
valid description of a object for answer, output”.
output”.
and satisfying the criteria for solution
Computer Algorithms Design and Analysis
The Class NP
A polynomial bounded nondeterministic
algorithm is one for which there is a (fixed)
polynomial function p such that for each input of size
n for which the answer is yes , there is some
execution of the algorithm that produces a yes
output in at most p(n) steps.
The class NP is the class of decision problems for
which there is a polynomial bounded
nondeterministic algorithm.
Computer Algorithms Design and Analysis
NP-complete Problems
A problem Q is NP-hard if every problem P in
NP is reducible to Q, that is P≤PQ.
(which means that Q is at least as hard as any
problem in NP )
A problem Q is NP-complete if it is in NP and
is NP-hard.
(which means that Q is at most as hard as to be
solved by a polynomially bounded
nondeterministic algorithm)
Computer Algorithms Design and Analysis
Polynomial Reduction
T(x)
x T Algorithm for Q
an input yes or no
(an input for Q answer
for P )
Algorithm for P
P (x)= yes ⇔ Q (T(x))= yes.
If x->T(x) is polynomial bounded, we said P is
polynimially reducable to Q, denoted as P≤PQ
(1)If P≤PQ, then Q is at least as “hard” to solve as P;
(2) If P≤PQ and Q is in class P, then P is in class P, and the cost of P is
bounded by p(n)+q(p(n))
Computer Algorithms Design and Analysis
Relation between P and NP
P ⊆ NP
NP ⊆ P? Not known yet!
Computer Algorithms Design and Analysis
Relation between NP , NP-hard and NPC
(1) They are different classes, NP≠NP-hard,
as there exists Halt problem, which in NP-
hard, but not in NP
(2)
NP NPC NP-hard
(3) If any NP-completed problem is proved in
P , then NP =P .
First Known NP-Complete Problem
Cook’ Theorem: SAT∈ NPC
Computer Algorithms Design and Analysis
Proof of Being in NP
Graph coloring is in NP
Description of the input and the certificate
Properties to be checked for an answer “yes”
There are n colors listed
Each ci is in the range 1,…,k
Scan the list of edges to see if a conflict exists
Proving that each of the above statement can be
checked in polynomial time.
Computer Algorithms Design and Analysis
Proving NPC by Reduction
The CNF-SAT problem is NP -complete.
Prove problem Q is NP-complete, given a
problem P known to be NP -complete
For all R∈NP, R≤PP;
Show P≤PQ;
By transitivity of reduction, for all R∈NP, R≤PQ;
So, Q is NP-hard;
If Q is in NP as well, then Q is NP-complete.
Computer Algorithms Design and Analysis
Known NP-Complete Problem
Garey & Johnson: Computer and Intractability: A
Guide to the Theory of NP-Completeness, Freeman,
1979
About 300 problems
i.e. SAT, Clique, Hamiltonian, Partition, Knapsack …
Note: 0-1 knapsack problem is NPC problem, but it can be solved by
using dynamic programming in polynomial time, think about why and
how? (You can refer to the exercise in CLRS page 384, ex 16.2-2,
which solution can be found in the instructor’s manual. ) Is that
means it in P? No, the DP algorithm is in a pseudo-polynomial time.
It is still exponential to its input size. The explanation can be found in
the textbook page 558, section 13.2.5.
