MODULE 5
Complexity Theory and Approximation Algorithms-Discussion
5.1. Computational Complexity Theory-Discussion
5.2. P, NP, NP-Complete, and NP-Hard Classes
5.3. Cook’s Theorem, Polynomial-Time Reductions
5.4. Approximation Algorithms--Discussion
5.5. Traveling Salesman Problem (TSP) Approximation
[Link] Theory
Complexity analysis is defined as a technique to characterise the time taken by an algorithm with
respect to input size (independent from the machine, language and compiler). It is used for
evaluating the variations of execution time on different algorithms.
What is the need for Complexity Analysis?
Complexity Analysis determines the amount of time and space resources required to execute
it.
It is used for comparing different algorithms on different input sizes.
Complexity helps to determine the difficulty of a problem.
often measured by how much time and space (memory) it takes to solve a particular problem
5.2 .P, NP, NP-Complete, and NP-Hard Classes:
Complexity classes are useful in organizing similar types of problems.
Types of Complexity Classes
This article discusses the following complexity classes:
P Class
The P in the P class stands for Polynomial Time. It is the collection of decision problems(problems
with a "yes" or "no" answer) that can be solved by a deterministic machine (our computers) in
polynomial time.
Features:
The solution to P problems is easy to find.
P is often a class of computational problems that are solvable and tractable. Tractable means
that the problems can be solved in theory as well as in practice. But the problems that can be
solved in theory but not in practice are known as intractable.
Most of the coding problems that we solve fall in this category like the below.
1. Calculating the greatest common divisor.
2. Finding a maximum matching.
3. Merge Sort
NP Class
The NP in NP class stands for Non-deterministic Polynomial Time. It is the collection of decision
problems that can be solved by a non-deterministic machine (note that our computers are
deterministic) in polynomial time.
Features:
The solutions of the NP class might be hard to find since they are being solved by a non-
deterministic machine but the solutions are easy to verify.
Problems of NP can be verified by a deterministic machine in polynomial time.
Example:
Let us consider an example to better understand the NP class. Suppose there is a company having a
total of 1000 employees having unique employee IDs. Assume that there are 200 rooms available for
them. A selection of 200 employees must be paired together, but the CEO of the company has the
data of some employees who can't work in the same room due to personal reasons.
This is an example of an NP problem. Since it is easy to check if the given choice of 200 employees
proposed by a coworker is satisfactory or not i.e. no pair taken from the coworker list appears on the
list given by the CEO. But generating such a list from scratch seems to be so hard as to be
completely impractical.
It indicates that if someone can provide us with the solution to the problem, we can find the correct
and incorrect pair in polynomial time. Thus for the NP class problem, the answer is possible, which
can be calculated in polynomial time.
This class contains many problems that one would like to be able to solve effectively:
1. Boolean Satisfiability Problem (SAT).
2. Hamiltonian Path Problem.
3. Graph coloring.
Co-NP Class
Co-NP stands for the complement of NP Class. It means if the answer to a problem in Co-NP is No,
then there is proof that can be checked in polynomial time.
Features:
If a problem X is in NP, then its complement X' is also in CoNP.
For an NP and CoNP problem, there is no need to verify all the answers at once in
polynomial time, there is a need to verify only one particular answer "yes" or "no" in
polynomial time for a problem to be in NP or CoNP.
Some example problems for CoNP are:
1. To check prime number.
2. Integer Factorization.
NP-hard class
An NP-hard problem is at least as hard as the hardest problem in NP and it is a class of problems
such that every problem in NP reduces to NP-hard.
Features:
All NP-hard problems are not in NP.
It takes a long time to check them. This means if a solution for an NP-hard problem is given
then it takes a long time to check whether it is right or not.
A problem A is in NP-hard if, for every problem L in NP, there exists a polynomial-time
reduction from L to A.
Some of the examples of problems in Np-hard are:
1. Halting problem.
2. Qualified Boolean formulas.
3. No Hamiltonian cycle.
NP-complete class
A problem is NP-complete if it is both NP and NP-hard. NP-complete problems are the hard
problems in NP.
Features:
NP-complete problems are special as any problem in NP class can be transformed or reduced
into NP-complete problems in polynomial time.
If one could solve an NP-complete problem in polynomial time, then one could also solve
any NP problem in polynomial time.
Some example problems include:
Hamiltonian Cycle.
Satisfiability.
Vertex cover.
Complexity Characteristic feature
Class
P Easily solvable in polynomial time.
NP Yes, answers can be checked in
polynomial time.
Co-NP No, answers can be checked in
polynomial time.
NP-hard All NP-hard problems are not in NP and
it takes a long time to check them.
NP- A problem that is NP and NP-hard is NP-
complete complete.
P, NP, NP-Complete and NP-Hard classes
NP stands for Non-deterministic Polynomial time.
Definition: P is a set of all decision problems solvable by a deterministic algorithm in polynomial
time.
Definition: NP is the set of all decision problems solvable by a nondeterministic algorithm in
polynomial time. This also implies P ⊆ NP
Problems known to be in P are trivially in NP — the nondeterministic machine just never troubles
itself to fork another process, and acts just like a deterministic one. One example of a problem not in
P but in NP is Integer Factorization.
But there are some problems which are known to be in NP but don’t know if they’re in P. The
traditional example is the decision-problem version of the Travelling Salesman Problem (decision-
TSP). It’s not known whether decision-TSP is in P: there’s no known poly-time solution, but there’s
no proof such a solution doesn’t exist.
There are problems that are known to be neither in P nor NP; a simple example is to enumerate all
the bit vectors of length n. No matter what, that takes 2n steps.
Now, one more concept: given decision problems P and Q, if an algorithm can transform a solution
for P into a solution for Q in polynomial time, it’s said that Q is poly-time reducible (or just
reducible) to P.
The most famous unsolved problem in computer science is “whether P=NP or P≠NP? ”
Figure: Commonly believed relationship between P and NP
Figure: Commonly believed relationship between P, NP, NP- Complete and NP-hard problems
Definition: A decision problem D is said to be NP-complete if:
1. it belongs to class NP
2. every problem in NP is polynomially reducible to D
The fact that closely related decision problems are polynomially reducible to each other is not very
surprising. For example, Hamiltonian circuit problem is polynomially reducible to the decision
version of the traveling salesman problem.
NP-Complete problems have the property that it can be solved in polynomial time if all other NP-
Complete problems can be solved in polynomial time. i.e if anyone ever finds a poly-time solution to
one NP-complete problem, they’ve automatically got one for all the NP-complete problems; that will
also mean that P=NP.
Example for NP-complete is CNF-satisfiability problem. The CNF-satisfiability problem deals with
boolean expressions. This is given by Cook in 1971. The CNF-satisfiability problem asks whether or
not one can assign values true and false to variables of a given boolean expression in its CNF form
to make the entire expression true.
Over the years many problems in NP have been proved to be in P (like Primality Testing). Still,
there are many problems in NP not proved to be in P. i.e. the question still remains whether P=NP?
NP Complete Problems helps in solving this question. They are a subset of NP problems with the
property that all other NP problems can be reduced to any of them in polynomial time. So, they are
the hardest problems in NP, in terms of running time. If it can be showed that any NP-Complete
problem is in P, then all problems in NP will be in P (because of NP-Complete definition), and
hence P=NP=NPC.
NP Hard Problems - These problems need not have any bound on their running time. If any NP-
Complete Problem is polynomial time reducible to a problem X, that problem X belongs to NP-Hard
class. Hence, all NP-Complete problems are also NP-Hard. In other words if a NP-Hard problem is
non-deterministic polynomial time solvable, it is a NP- Complete problem. Example of a NP
problem that is not NPC is Halting Problem.
If a NP-Hard problem can be solved in polynomial time then all NP-Complete can be solved in
polynomial time.
“All NP-Complete problems are NP-Hard but not all NP-Hard problems are not NP- Complete.”NP-
Complete problems are subclass of NP-Hard
The more conventional optimization version of Traveling Salesman Problem for finding the shortest
route is NP-hard, not strictly NP-complete.
The preorder traversal of the tree is found to be − 1 → 2 → 5 → 6 → 3 → 4
Step 3
Adding the root node at the end of the traced path, we get, 1 → 2 → 5 → 6 → 3 → 4 → 1
This is the output Hamiltonian path of the travelling salesman approximation problem. The
cost of the path would be the sum of all the costs in the minimum spanning tree, i.e., 55.