Sanjivani Rural Education Society’s

Sanjivani College of Engineering, Kopargaon-423 603

(An Autonomous Institute, Affiliated to Savitribai Phule Pune University, Pune)
NAAC ‘A’ Grade Accredited, ISO 9001:2015 Certified

Department of Computer Engineering

(NBA Accredited)

Subject- Design and Analysis of Algorithms (DAA) [CO 301)]

Unit 5:- Complexity Theory

Prof. Abhijit S. Bodhe

Assistant Professor
Department of Computer Engineering
E-mail :
[email protected]
Contact No: 7709 340 570
 Unit 5:- Complexity Theory
• Polynomial and Non-Polynomial Class Problems,
• Deterministic and Non Deterministic Algorithms,
• P class problems, NP class problems.
• NP complete class problems- Vertex cover problem, 3-SAT problem
• NP-Hard Problems: Clique problem.
• Case Study:- Reduction problem (3SAT to Clique Problem).
• Application of Complexity: Visiting All the Cities in State, Country and
Globe

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 2

 Complexity Theory

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 3

 Polynomial and Non Det.-polynomial problems
• In Computer Science, many problems are solved where the objective is to
maximize or minimize some values, whereas in other problems we try to find
whether there is a solution or not. Hence, the problems can be categorized as
1. Optimization Problem:- For which the objective is to maximize or minimize
some values. For example,
a) Finding the minimum number of colors needed to color a given graph.
b) Finding the shortest path between two vertices in a graph.
2. Decision Problem:-for which the answer is a Yes or a No. For example,
a) Whether a given graph can be colored by only 4-colors.
b) Finding Hamiltonian cycle in a graph is not a decision problem, whereas
checking a graph is Hamiltonian or not is a decision problem.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 4
 Polynomial Class problems
• For input size n, if worst-case time complexity of an algorithm is O(nk),
where k is a constant, the algorithm is a polynomial time algorithm.
• Algorithms such as Matrix Chain Multiplication, Single Source Shortest Path,
All Pair Shortest Path, Minimum Spanning Tree, etc. run in polynomial time
• The class P consists of those problems that are solvable in polynomial time, i.e.
these problems can be solved in time O(nk) in worst-case, where k is constant.
• These problems are called tractable, while others are called intractable.
• an algorithm is polynomial time algorithm, if there exists a
polynomial p(n) such that the algorithm can solve any instance of size n in a
time O(p(n)).

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 5

 Deterministic Vs. Non- deterministic Algorithm
Key Deterministic Algorithm Non-deterministic Algorithm
Definition The algorithms in which the result of every The algorithms in which the result of every
algorithm is uniquely defined.OR algorithm is not uniquely defined and result
Algorithm that performs fixed number of steps
and always get finished with an accept or
could be random.
reject state with the same result.
Execution The path of execution for algorithm is The path of execution is not same for algorithm in
path every execution and could take any random path for
same in every execution.
execution.
Execution As outcome is known and is consistent Outcome is not known and is non-consistent on
Time
on different executions so it takes different executions so Non-Deterministic algorithm
could not get executed in polynomial time.
polynomial time for their execution.
Outcome It has a single outcome. It has multiple outcomes.
Example : Mathematical function is deterministic. Random function is non-deterministic.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 6
 P & NP problems
• Summary:- The problem belongs to class P if it’s easy to find a
solution for the problem. The problem belongs to NP, if it’s easy to
check a solution that may have been very tedious to find.
• If we produce an output according to the given input within a specific
amount of time such as within a minute, hours. This is known as
Polynomial time.
• The term "NP" does not mean "not polynomial." Originally, the term
meant "non-deterministic polynomial. It means according to the one
input number of output will be produced.

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 7

 In-Tractable/Traceable problems
• Problems that have a reasonable (polynomial) time solutions, are called
tractable/Traceable.
• Problems that have no reasonable (polynomial) time solutions, are called
intractable/In-Traceable.
• The Problems which can not be solved in reasonable amount of time. Or
Problems with exponential Complexity called In-traceable problems.
• The Travelling Salesman Problem is an example of an intractable problem
• A guessed solution to an intractable problem can be checked quickly. This is
called an NP-type problem e.g. College timetabling.

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 8

Tractable vs. In tractable Systems

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 9

 NP Problems
• The set of all decision-based problems came into the division of NP
Problems, who can't be solved or produced an output within polynomial
time but verified in the polynomial time called NP Problems.
• Many problems are hard to solve, but they have the property that it easy
to authenticate the solution if one is provided called NP Hard.
• NP class contains P class as a subset. Usually NP problems being hard
to solve than P class problems.
• If we produce an output according to the given input but there are no
time constraints, is known as Non Deterministic-Polynomial time. But
yes output will produce but time is not fixed yet (Depend on input).

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 10

 Relation of P and NP classes
• P contains in NP:-Observe that P contains in NP., if we can solve a
problem in polynomial time, we can indeed verify the solution in
polynomial time.
• More formally, we do not need to see a certificate (there is no need to
specify the specific path to solution) to solve the problem; we can explain
it in polynomial time.
• P=NP:-However, it is not known whether P = NP. It seems you can verify
and produce an output of the set of decision-based problems in NP classes
in a polynomial time, which is impossible because according to the
definition of NP classes you can verify the solution within the polynomial
time. So this relation can never be held.

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 11

Representation of all NP classes

• A problem is NP-
complete ,if the
problem is both –
NP-hard, and – NP.

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 12

P class & NP class problems

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 13

 Reduction in NP
• The class NP-complete (NP-C) problems consist of a set of decision
problems (a subset of class NP) that no one knows how to solve
efficiently.
• But if there were a polynomial solution for even a single NP-complete
problem, then every problem in NPC will be solvable in polynomial
time. For this, we need the concept of reductions.
• Example :- A problem R(NP-H) can be reduced to another problem Q;
if any instance of R can be rephrased to an instance of Q, the solution
to which provides a solution to the instance of R; This rephrasing is
called a transformation leads reduction.
• Refer :- https://www.javatpoint.com/daa-polynomial-time-verification

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 14

 Reduction
• A very simple example of a reduction is from multiplication to squaring.
Suppose all we know how to do is to add, subtract, take squares, and
divide by two. We can use this knowledge, combined with the following
formula, to obtain the product of any two numbers:

• However, the reduction becomes much harder if we add the restriction

that we can only use the squaring function one time, and only at the end.
In this case, even if we're allowed to use all the basic arithmetic
operations, including multiplication, no reduction exists in general

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 15

 vertex cover Problem
• The vertex cover problem is an NP-complete problem
• Statement:- Given a graph G(V, E) and a positive integer k, the
problem is to find whether there is a subset V’ of vertices of size at
most k, such that every edge in the graph is connected to some vertex
in V’.
• Since an NP Complete problem, by definition, is a problem which is
both in NP and NP hard, the proof for the statement that a problem is
NP Complete consists of two parts:
• Proof that vertex cover is in NP –
• Proof that vertex cover is NP Hard-
• https://www.geeksforgeeks.org/proof-that-vertex-cover-is-np-complete/

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 16

 Vertex cover is in NP –
• If any problem is in NP, then, given a ‘certificate’ (a solution) to the
problem and an instance of the problem (a graph G and a positive
integer k, in this case), we will be able to verify (check whether the
solution given is correct or not) the certificate in polynomial time.
• The certificate for the vertex cover problem is a subset V’ of V, which
contains the vertices in the vertex cover. We can check whether the set
V’ is a vertex cover of size k using random strategy
(for a graph G(V, E)):

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 17

 Proof that vertex cover is NP Hard –
• To prove that Vertex Cover is NP Hard, we take some problem which
has already been proven to be NP Hard, and show that this problem
can be reduced to the Vertex Cover problem. For this, we consider the
Clique problem.
• we can say that there is a clique of size k in graph G if and only if
there is a vertex cover of size |V| – k in G’, and hence, any instance of
the clique problem can be reduced to an instance of the vertex cover
problem, Shows that Vertex cover problem is NP hard.

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 18

 vertex cover Problem

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 19

 Clique decision problem
• Clique Decision problem is NP-Hard.
• “In computer science, the clique problem is the computational
problem of finding cliques (subsets of vertices, all adjacent to each
other, also called complete sub graphs) in a graph.”
• Given a small graph with N nodes and E edges, the task is to find the
maximum clique in the given graph. A clique is a complete sub-graph
of a given graph. This means that all nodes in the said sub-graph are
directly connected to each other, or there is an edge between any two
nodes in the sub-graph.
• The maximal clique is the complete sub-graph of a given graph which
contains the maximum number of nodes.

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 20

Clique decision problem

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 21

 3-SAT Problem
• 3-SAT is NP-complete.
• 3SAT, or the Boolean satisfiability problem, is a problem that asks
what is the fastest algorithm to tell for a given formula in Boolean
algebra (with unknown number of variables) whether it is satisfiable,
that is, whether there is some combination of the (binary) values of the
variables that will give 1.

• Eg:- (x ∨ x ∨ y) ∧ (¬x ∨ ¬y ∨ ¬y) ∧ (¬x ∨ y ∨ y)

• 3 SAT to Cilique reduction process:-
• https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/threeSAT_to_clique.html

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 22

 3-SAT Problem
• The 3-SAT instance (x ∨ x ∨ y) ∧ (¬x ∨ ¬y ∨ ¬y) ∧ (¬x ∨ y ∨ y) reduced
to a clique problem. The green vertices form a 3-clique and
correspond to the satisfying assignment x=FALSE, y=TRUE.

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 23

 Clique problem Reduction
• Proof that the Boolean Satisfiability problem reduces to the Clique Decision Problem.

• Therefore, the Clique Decision Problem is NP-Hard.

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 24

Reduction of 3SAT to Clique

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 25

Reduction of 3SAT to Clique

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 26

 Reduction of vertex cover to clique
• Clique is called a subset of vertices that are all directly connected.
It determines whether a clique of size k exists in a graph.
• To prove − Vertex cover can be reduced to clique.
1. Given a graph G=(V,E) and integer k.
2. Get its complement graph G'=(V,E').
3. Solve CLIQUE(G',|V|-k).
4. If there is a solution, return yes. Otherwise, it returns as no.
5. To prove this reduction, we need to show the following −

https://www.tutorialspoint.com/prove-that-the-polynomial-time-
reduction-is-from-the-clique-problem-to-the-vertex-cover-problem
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 27
 Reduction of vertex cover to clique
I. If there is a solution to VERTEX-COVER(G,k), then there must be a solution to
CLIQUE(G',|V|-k) and vice versa.
II. Assume that G has a vertex cover V' ⊆ V , where |V |' = k. Then, for all u, v ε V
, if (u, v) ε E, then u ε V' or v ε V' or both since the vertex cover must cover all
edges.
III. The contrapositive is that for all u, v ε V, if u does not belong to V', then (u, v)
ε/ E and thus (u, v) ε E.
IV. For any pair of vertices that are both not in the vertex cover V' of G, there is an
edge between them in G. The union of all pairs of vertices that are all not in V'
is simply V − V'. Thus, V − V' is a clique in G, by definition, and V − V' has
size |V | − k.
• This operation can be done in polynomial time. Since VERTEX-COVER can be
reduced to CLIQUE in polynomial time, CLIQUE ε NP and VERTEX-COVER is
NP-complete, CLIQUE is also NP-Complete.
DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 28
Vertex cover to clique Reduction

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 29

 Unit 5:- Complexity Theory
• Polynomial and Non-Polynomial Class Problems,
• Deterministic and Non Deterministic Algorithms,
• P class problems, NP class problems.
• NP complete class problems- Vertex cover problem, 3-SAT problem
• NP-Hard Problems: Clique problem.
• Case Study:- Reduction problem (3SAT to Clique Problem).
• Application of Complexity: Visiting All the Cities in State, Country and
Globe

DEPARTMENT OF COMPUTER ENGINEERING, Sanjivani COE, Kopargaon 30