Design & Analysis of Algorithms
Theory of NP Completeness
Overview
• NP-complete problems are in NP, the set of all
decision problems whose solutions can be verified
in polynomial time.
• NP may be equivalently defined as the set of
decision problems that can be solved in
polynomial time on a non-deterministic Turing
machine.
• A problem p in NP is NP-complete if every other
problem in NP can be transformed (or reduced)
into p in polynomial time.
Can all computational problems be
solved by a computer?
• There are computational problems that can not be solved by
algorithms even with unlimited time.
• For example, Turing Halting problem.
– Alan Turing proved that general algorithm to solve the
halting problem for all possible program-input pairs
cannot exist.
– A key part of the proof is, Turing machine was used as a
mathematical definition of a computer and program.
• Status of NP Complete problems is another failure story, these
are problems are problems whose status is unknown.
• No polynomial time algorithm has yet been discovered for any
NP complete problem, nor has anybody yet been able to
prove that no polynomial-time algorithm exist for any of them.
• If any one of the NP complete problems can be solved
in polynomial time, then all of them can be solved.
What are NP, P, NP-complete and
NP-Hard problems?
• P is set of problems that can be solved by a deterministic Turing machine in
Polynomial time.
• NP is set of decision problems that can be solved by a Non-deterministic Turing
Machine in Polynomial time.
– P is subset of NP
– Informally, NP is set of decision problems which can be solved by a
polynomial time via a “Lucky Algorithm”, a magical algorithm that always
makes a right guess among the given set of choices.
What are NP, P, NP-complete and
NP-Hard problems?
• A problem is NP-hard if all problems in NP are polynomial time reducible to it, even
though it may not be in NP itself.
– The circuit-satisfiability problem
– Set Cover
– Vertex Cover
– Travelling Salesman Problem
• A problem is NP-complete if it is both NP-hard and in NP. Therefore, NP-Complete
set is also a subset of NP-Hard set.
– Determining whether a graph has a Hamiltonian cycle
– Determining whether a Boolean formula is satisfiable, etc.
What are NP, P, NP-complete
and NP-Hard problems?
P versus NP problem
• The P versus NP problem is a major unsolved problem in
computer science. It asks whether every problem whose
solution can be quickly verified can also be solved quickly.
• It is one of the seven Millennium Prize Problems selected by
the Clay Mathematics Institute, each of which carries a
US$1,000,000 prize for the first correct solution.
P versus NP problem
• An answer to the P versus NP question would determine whether problems
that can be verified in polynomial time can also be solved in polynomial
time.
• If it turned out that P ≠ NP, which is widely believed, it would mean that
there are problems in NP that are harder to compute than to verify: they
could not be solved in polynomial time, but the answer could be verified in
polynomial time.
P versus NP problem
Decision vs Optimization Problems
• NP-completeness applies to the realm of decision problems.
• It was set up this way because it’s easier to compare the
difficulty of decision problems than that of optimization
problems.
• In reality, though, discussing the difficulty of decision problems
is often really equivalent to discussing the difficulty of
optimization problems.
• For example, consider the vertex cover problem (Given a
graph, find out the minimum sized vertex set that covers all
edges). It is an optimization problem. Corresponding decision
problem is, given undirected graph G and k, is there a vertex
cover of size k?
What is Reduction?
• Let L1 and L2 be two decision problems.
• Suppose algorithm A2 solves L2. That is, if y is an input for L2
then algorithm A2 will answer Yes or No depending upon
whether y belongs to L2 or not.
• The idea is to find a transformation from L1 to L2 so that the
algorithm A2 can be part of an algorithm A1 to solve L1.
What is Reduction?
• Learning reduction in general is very important.
• For example, if we have library functions to solve certain problem and if we
can reduce a new problem to one of the solved problems, we save a lot of
time.
• Consider the example of a problem where we have to find minimum product
path in a given directed graph where product of path is multiplication of
weights of edges along the path. If we have code for Dijkstra’s algorithm to
find shortest path, we can take log of all weights and use Dijkstra’s algorithm
to find the minimum product path rather than writing a fresh code for this new
problem.
How to prove that a given problem is NP
complete?
• From the definition of NP-complete, it appears
impossible to prove that a problem L is NP-Complete.
By definition, it requires us to that show every problem in
NP is polynomial time reducible to L.
• Fortunately, there is an alternate way to prove it. The
idea is to take a known NP-Complete problem and
reduce it to L. If polynomial time reduction is possible, we
can prove that L is NP-Complete by transitivity of
reduction (If a NP-Complete problem is reducible to L in
polynomial time, then all problems are reducible to L in
polynomial time).
What was the first problem proved
as NP-Complete?
• There must be some first NP-Complete problem proved by
definition of NP-Complete problems. SAT (Boolean
satisfiability problem) is the first NP-Complete problem proved
by Cook.
• It is always useful to know about NP-Completeness even for
engineers.
✔ Suppose you are asked to write an efficient algorithm to solve
an extremely important problem for your company. After a lot
of thinking, you can only come up exponential time approach
which is impractical.
✔ If you don’t know about NP-Completeness, you can only say
that I could not come with an efficient algorithm.
✔ If you know about NP-Completeness and prove that the
problem as NP-complete, you can proudly say that the
polynomial time solution is unlikely to exist.