Transcript ppt - Crystal

ADVANCED COMPUTATIONAL MODELS
AND ALGORITHMS
Instructor: Dr. Gautam Das
Lecture 3
January 29, 2009
Class notes by Alexandra Stefan
• Review (see previous lecture):
– optimization problem, decision problem, verification
problem;
– P, NP;
– polynomial time reduction;
• Overview of lecture:
– New definitions:
• Decision problem as a set, complement of a decision
problem, Co-NP, NP-Complete
– Example problems used or mentioned:
• HCP, TSP, SP, PRIME, SATISFIABILITY
(HCP = Hamiltonian Cycle, TSP = Traveling Salesman, SP = Shortest Path )
– Other things to remember:
• Pay attention to the proper formulation of what constitutes the input
of each problem.
• It is not always easy to produce a certificate for a decision problem.
Definitions
• NP
– set of problems whose verification version can be solved in polynomial
time.
– Imporatnt: You need to have a certificate
• Decision problems as sets:
– A decision problem takes an input and produces an ‘Yes’ or ‘No’ output.
– Any decision problem, X, can be defined as the set of inputs for which
the answer is ‘Yes’.
• The complement of a decision problem:
– Given a decision problem X, the complement of X is the set of inputs for
which the answer is ‘No’.
• Co-NP = set of decision problems whose complement problem is in NP.
• NP-Complete: A problem X is NP-Complete if:
– X is NP
– Any NP problem Y can be reduced in polynomial time to X. (“X should be
the hardest problem in it’s class”)
(Intuition: finding an NP-Complete problem is like finding the largest number
in a set of numbers)
NP
NP-Complete
NP
Co-NP
P
P
SP – Shortest Path
• SP
– Input: G (graph) ,s (vertex), t (vertex), x (value)
– Output:
• ‘Yes’ if there exists a path from s to t of length less or equal to x.
• ‘No’, otherwise.
• SP is in NP:
– Certificate: list of vertices
– Easy to check if the certificate is a valid path, to compute it’s length and
compare it with x.
• SP is in Co-NP:
– Certificate: nothing
– use Dijkstra to get the shortest path and it’s length, y. This runs in
polynomial time.
– Compare x with y.
• Set version of SP:
– The set of tuples: < G (graph) ,s (vertex), t (vertex), x (value) > for which
the answer is ‘Yes’.
Hamiltonian Cycle Problem (HCP)
• Definition:
– Input: unweighted graph
– Output:
• Yes, if there exists a cycle that visits all vertices exactly once
• No, otherwise
• Examples
Graph:
Does it have a Hamiltonian cycle?
Answer:
No
Yes
Hamiltonian Cycle Problem (HCP)
• Is HCP in NP ?
– Yes
– A certificate is a list of vertices
– It is easy to verify that the certificate
constitutes a valid cycle in the graph and that
it covers all vertices
• Is HCP in Co-NP ?
– yes
– Since HCP is in NP
NP-Complete
• How do you show that a problem is NP-Complete?
– You have to show that any problem in NP can be reduced to it.
• First problem that was shown to be NP-Complete
– is the SATISFIABILITY problem.
– It is known as Cook’s Theorem.
• Once we have an NP-Complete problem, X, to show that
another NP problem, Y, is NP-Complete, we only need to
show that X reduces in polynomial time to Y.
NP-Complete
Y
X
If X is NP-Complete and
X reduces in polynomial time to Y
then any problem can be reduced
in polynomial time to Y by
First reducing it to X and
then reducing X to Y.
(Here we used the property of
polynomials of being closed
under multiplication.)
Polynomial reduction
3 equivalent ways of saying that X reduces in polynomial time to Y:
Solver of X
(using reduction of X to Y)
Input for X
reducer
Solver of Y
answer
Set mapping after reduction
X
p Y
X
Y
X
Universe of inputs for X
Y
Universe of inputs for Y
PRIME
• PRIME
NP
– Input: number n (of m bits)
– Output: Is n a prime number
or not?
Co-NP
PRIMES
• First believed to be NP.
• First shown to be both in
NP and Co-NP.
• Then shown to be in P.
PRIMES
P