Module 5

Introduction to Complexity Theory

Computational problems can be broadly classified into
solvable and unsolvable problems.

Solvable problems are problems that have an algorithm

running in finite time whereas for unsolvable problems,
every algorithm takes infinite time to complete.

Eg: Problems such as sorting and searching are solvable.

printing all natural numbers, printing all real numbers,

and halting problem are unsolvable.
1
This brings a classification among solvable
computational problems, namely tractable and
intractable problems.

Tractable : Problems that can be solvable in a reasonable

(polynomial) time. ie A problem is tractable if there exists
a polynomial-time algorithm

Intractable : Some problems are intractable, as they

grow large, we are unable to solve them in reasonable
time or there does not exists a polynomial-time
algorithm.
 Tractability
• What constitutes reasonable time?
– Standard working definition: polynomial time
– On an input of size n the worst-case running time is
O(nk) for some constant k

– Polynomial time: O(n2), O(n3), O(1), O(n lg n)

– Not in polynomial time: O(2n), O(nn), O(n!)

5
Interestingly, there are computational
problems like
travelling salesperson problem,
maximum clique problem,
minimum vertex cover problem,etc.,
for which, as of this date, there is no known
polynomial-time algorithm, nor do they have
exponential-time lower bound.

That is, such problems cannot be included

either in tractable or intractable class. We
call such problems as HARD problems.
To cope up with HARD problem and to
understand the inherent difficulty of the
problem, we ask;
can the computational model be altered
so that it is different from the traditional
deterministic computations?

Motivated by this line of research, we

introduce the non-deterministic model in
which the computational graph is a tree
instead of a path.
The non-deterministic computation takes a
non-deterministic move (guess) at each
step of the computation. The sequence of
correct guesses constitute a solution which
is a path in the associated tree.

We can see the non-deterministic model as

a powerful model that is capable of
computing more tasks at once and produces
the correct solution if the input has one
such solution.
Non-deterministic machine is a hypothetical
machine (cannot be realized in practice) and
the objective of introducing this machine is
to understand the computational complexity
of the problem in hand. Questions such as
how difficult the problem is over other
problems, the inherent complexity of the
problem, etc., can be answered better under
this model.

This line of study was introduced by

researchers Stephen Cook and Leonid Levin.
Subsequently, they introduced complexity
classes P and NP.
Let us revisit tractable (intractable)
problems.
Tractable : tractable problems are problems that have
polynomial-time algorithms under a deterministic
computational model.
Intractable : intractable problems are problems that
does not exists a polynomial-time algorithm or exists
exponential-time algorithms under a deterministic
computational model.
 Optimization/Decision Problems
• Optimization Problems
- An optimization problem asks us to find, among all feasible
solutions, one that maximizes or minimizes a given objective
- Examples:
Shortest Path, longest Path, Minimum Spanning Tree,
Minimum Vertex Cover, Maximum Independent Set,
Maximum Clique
• Decision Problems
– A decision problem is one with yes/no answer
– Examples:
Given a graph G,
– Does there exist a Path of length k?
– Does there exist a Spanning tree whose total cost is k?
– Does there exist a vertex cover of size k?
– Does there exist a clique of size k? 12
 Optimization/Decision Problems
• An optimization problem tries to find an optimal solution
• A decision problem tries to answer a yes/no question
• Many problems will have decision and optimization versions
– Eg: Traveling salesman problem
• optimization: find hamiltonian cycle of minimum
weight
• decision: is there a hamiltonian cycle of weight k

Since optimization problems have equivalent decision problems, we

shall focus on decision problems and let us define the complexity
classes restricted to decision problems.

13
Complexity Classes:
-P
- NP
- NP-Hard
- NP-Complete

14
 The Class P

P : the class of decision problems that are solvable in

deterministic polynomial time. That is, they are
solvable in O(p(n)), where p(n) is a polynomial on n

P={ X : X is a decision problem and X is solvable in deterministic polynomial time }

Sample Problems in P

• MST
• Sorting
• Shortest path
15
 The class NP
NP : the class of decision problems that are solvable in polynomial time on a
nondeterministic machine (or with a nondeterministic algorithm)

• Think of a nondeterministic computer as a parallel machine that can

freely spawn an infinite number of processes
• Thus NP can also be thought of as the class of problems “whose solutions
can be verified in polynomial time”
• Note that NP stands for “Nondeterministic Polynomial-time”

NP={ X : X is a decision problem and X is solvable in non-deterministic polynomial time }

or

NP={ X : there exists a deterministic polynomial-time algorithm to verify an instance of X}

16
 Sample Problems in NP
– Traveling Salesman
– Graph Coloring
– Satisfiability (SAT)
– Minimum Vertex Cover
– Maximum Independent Set
– Maximum Clique

17
 P and NP

• P is the class of all decision problems that

can be solved in polynomial time under
deterministic model.
• NP is the class of all decision problems that
can be verified in polynomial time: – any
“yes-instances” can be checked in
polynomial time with the help of a short
certificate.
• Clearly, P ⊆ NP
 Class co-NP

•co-NP is the class of all decision problems

whose no answers can be verified in polynomial
time:
– any “no-instances” can be checked in
polynomial time with the help of a short
certificate.

Clearly, P ⊆ NP ∩ co-NP
A Technique for solving Problems - Reduction

Reductions between problems

• A polynomial-time reduction from a decision
problem A to a decision problem B is a
procedure that transforms any instance IA of A
into an instance IB of B with the following
characteristics:
– the transformation takes polynomial time
– the answer for IA is yes iff the answer for IB is
yes
• We say that A ≤P B (Problem A is polynomially
reduced to Problem B)
Reductions between problems

• Reductions are useful for optimization problems as

well
 Reductions - consequences

• If A is “hard”, then B should be hard too ....

Class NP-Complete
One view of various classes ...
 CLIQUE
● A Clique in an undirected graph G (V,E) is a subset V’ ⊆ V of
vertices, such that each pair of which is connected by an edge in
E.
● Clique is a complete subgraph of G.
● size of a clique is the number of vertices it contains.
● Clique problem:
Optimization problem: Find a clique of maximum size in a
graph.
Decision Problem Does there exists a clique of a given size k in
the graph G?
A k-clique is a clique that contains k nodes
 Vertex Cover
A set S ⊂ V (G) is called a vertex cover of G if for every
edge uv ∈ E(G) either u or v or both are in S.

Vertex Cover problem:

Optimization problem
Input: Graph G with the vertex set V (G) = {v1, . . . , vn}
and the edge set E(G)
Question: Find a Minimum Vertex Cover.

Decision Vertex Cover:

Input: Graph G, Integer k
Question: Does there exists a vertex cover of size k in the
graph?
NP-Completeness proof

Steps to prove that the given problem is NP- Complete

1. Prove that the given problem is NP.
- Write a polynomial time verification algorithm.
2. Prove that the given problem is NP-Hard
- Write a polynomial time reduction algorithm from any known
NP – Complete problem to the given problem