Module 8-

NP Completeness
CO6 - Make use ofthe complexity classes like NP-Complete, NP-hard
and develop polynomial reductions for the real world problems
Limitations of the algorithm
Power/Computational Complexity of
the Problem
TRACTABLE INTRACTABLE

As they (Problem) grow large, we are As they grow large, we are unable to
able to solve them in reasonable time solve them in reasonable time

The lower bound suggests the The upper bound suggests the
problem is tractable problem is intractable

O(N) O(2n), O(nn), O(n!)

Optimization/Decision Problems
• Optimization Problems
– An optimization problem is one which asks, “What
is the optimal solution to problem X?”
– Examples:
• 0-1 Knapsack
• Fractional Knapsack
• Minimum Spanning Tree
• Decision Problems
– An decision problem is one with yes/no answer
– Examples:
• Does a graph G have a MST of weight  W?
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
• Some problems are decidable, but intractable:
as they grow large, we are unable to solve them in
reasonable time
– Is there a polynomial-time algorithm that solves the problem?
“Hard” and “easy’ Problems
• Sometimes the dividing line between “easy” and
“hard” problems is a fine one. For example
– Find the shortest path in a graph from X to Y. (easy)
– Find the longest path in a graph from X to Y. (with no cycles)
(hard)
• View another way – as “yes/no” problems
– Is there a simple path from X to Y with weight <= M? (easy)
– Is there a simple path from X to Y with weight >= M? (hard)
– First problem can be solved in polynomial time.
– All known algorithms for the second problem (could) take
exponential time .

Young CS 331 D&A of Algo. NP-Completeness 5

General Problems, Input Size and
Time Complexity
• Time complexity of algorithms :
polynomial time algorithm ("efficient algorithm") v.s.
exponential time algorithm ("inefficient algorithm")
f(n) \ n 10 30 50

n 0.00001 sec 0.00003 sec 0.00005 sec

n5 0.1 sec 24.3 sec 5.2 mins

2n 0.001 sec 17.9 mins 35.7 yrs

Young CS 331 D&A of Algo. NP-Completeness 6

Computational Complexity Classes
P NP
P stands for “Polynomial time” NP stands “Nondeterministic Polynomial-
time”

the class of decision problems that set of problems for which a solution can
can be solved /run in polynomial-time be verified in polynomial time

A deterministic algorithm is (essentially) A nondeterministic algorithm is one that

one that always computes the ‘P’ class can “guess” the right answer or solution
problem with correct answer
Fractional Knapsack, Sorting, MST •Hamiltonian Cycle (Traveling Salesman)
•Graph Coloring
•Satisfiability (SAT)
NP-Complete
• It is also interesting to look at the relationship
between some easy problems and hard ones:
NP and P
• What is NP?
• NP is the set of all decision problems (question with yes-or-
no answer) for which the 'yes'-answers can be verified in
polynomial time (O(n^k) where n is the problem size, and k
is a constant) by a deterministic Turing machine.
Polynomial time is sometimes used as the definition of fast
or quickly.
• What is P?
• P is the set of all decision problems which can be solved in
polynomial time by a deterministic Turing machine. Since it
can solve in polynomial time, it can also be verified in
polynomial time. Therefore P is a subset of NP.
NP-complete problems
• A decision problem D is NP-complete iff
1. D  NP
2. every problem in NP is polynomial-time reducible
to D

• Cook’s theorem (1971): CNF-sat is NP-

complete
NP-Complete
• What is NP-Complete?
• A problem x that is in NP is also in NP-Complete if
and only if every other problem in NP can be
quickly (ie. in polynomial time) transformed into
x. In other words:
– x is in NP, and
– Every problem in NP is reducible to x
• So what makes NP-Complete so interesting is
that if any one of the NP-Complete problems was
to be solved quickly then all NP problems can be
solved quickly
NP-Hard
• What is NP-Hard?
• NP-Hard are problems that are at least as hard
as the hardest problems in NP.
• Note that NP-Complete problems are also NP-
hard.
• Obvious : P  NP, i.e. A NP
(decision) problem in P does
not need “guess solution”.
The correct solution can be P
computed in polynomial time.

• Some problems which are in NP, but may not in P :

• 0/1 Knapsack Problem
• PARTITION Problem : Given a finite set of positive integers Z.
Question : Is there a subset Z' of Z such that
Sum of all numbers in Z' = Sum of all numbers in Z-Z' ?
i.e.  Z' =  (Z-Z')

Young CS 331 D&A of Algo. NP-Completeness 13

Certificat
es
• Returning true: in order to show that the
schedule can be made, we only have to show
one schedule that works
– This is called a certificate.

• Returning false: in order to show that the

schedule cannot be made, we must test all
schedules.
Deterministic Algorithm
Vs Non-deterministic Algorithm
Deterministic Algorithm Non-deterministic Algorithm

For a particular input the computer will give For a particular input the computer will give
always same output. different output on different execution.

Can solve the problem in polynomial time. Can’t solve the problem in polynomial time.

Cannot determine the next step of execution

Can determine the next step of execution. due to more than one path the algorithm can
take.
Determinism vs. Nondeterminism

• Nondeterministic algorithms produce an answer by

a series of “correct guesses”

• Deterministic algorithms (like those that a

computer executes) make decisions based on
information.
• Some of the terms related to the non-
deterministic algorithm are defined below:
• choice(X) : chooses any value randomly from
the set X.
• failure() : denotes the unsuccessful solution.
• success() : Solution is successful and current
thread terminates.
NP-Complete
“NP-Complete” comes from:
– Nondeterministic Polynomial
– Complete - “Solve one, Solve them all”

There are more NP-Complete problems than provably

intractable problems.
• NP Problem: 
The NP problems set of problems whose solutions are hard to find but easy to
verify and are solved by Non-Deterministic Machine in polynomial time. 
• NP-Hard Problem: 
A Problem X is NP-Hard if there is an NP-Complete problem Y, such that Y is
reducible to X in polynomial time. NP-Hard problems are as hard as NP-Complete
problems. NP-Hard Problem need not be in NP class.
• NP-Complete Problem: 
• A problem X is NP-Complete if there is an NP problem Y, such that Y is reducible to
X in polynomial time. NP-Complete problems are as hard as NP problems. A
problem is NP-Complete if it is a part of both NP and NP-Hard Problem. A non-
deterministic  Turing machine can solve NP-Complete problem in polynomial
time. 
NP-hard NP-Complete

NP-Hard problems(say X) can be solved if and only if there is a

NP-Complete problems can be solved by a non-deterministic
NP-Complete problem(say Y) that can be reducible into X in
Algorithm/Turing Machine in polynomial time.
polynomial time.

To solve this problem, it must be both NP and NP-hard

To solve this problem, it do not have to be in NP .
problems.

Do not have to be a Decision problem. It is exclusively a Decision problem.

Example: Determine whether a graph has a Hamiltonian cycle,

Example: Halting problem, Vertex cover problem, etc. Determine whether a Boolean formula is satisfiable or not,
Circuit-satisfiability problem, etc.
• P: (Decision) problems solvable by deterministic
algorithms in polynomial time
• NP: (Decision) problems solved by non-deterministic
algorithms in polynomial time
• A group of (decision) problems,
including all of the ones we have
NP-Complete
discussed (Satisfiability, 0/1
Knapsack, Longest Path, Partition)
have an additional important
NP
property:
If any of them can be solved in
P
polynomial time, then they all
can!
• These problems are called NP-complete problems.
Young CS 331 D&A of Algo. NP-Completeness 23
Intro to Boolean Algebra
negation: not ()
literal: (negated or not) Boolean variable conjunction: and ()
Examples: x, x disjunction: or ()
clause: several literals connected with 
Example: (xyz)
CNF (Conjunctive Normal Form): several clauses connected with 
Example: (x y)(xyz)
3CNF: a CNF formula with three literals in each clause.
Example: (xyz)(xyz)
The Satisfiability (SAT) Problem
• Satisfiability (SAT):
– Given a Boolean expression on n variables, can we
assign values such that the expression is TRUE?
– Ex: ((x1 x2)  ((x1  x3)  x4)) x2
– Seems simple enough, but no known deterministic
polynomial time algorithm exists
– Easy to verify in polynomial time!
Circuit-SAT

Logic Gates 0 1 0
1 1
NOT
1 1
0
OR 1
0 0 1
1

AND

• Take a Boolean circuit with a single output node and

ask whether there is an assignment of values to the
circuit’s inputs so that the output is “1”
2-CNF SAT
• Each or operation has two arguments that are
either variables or negation of variables
• The problem in 2 CNF SAT is to find
true/false(0 or 1) assignments to the variables
in order to make the entire formula true.

(xy)(yz)(xz)(zy)
• Any of the OR clauses can be converted to
implication clauses
2-SAT is in P
• Create the implication graph

x

y
x

y

z

z
Satisfiability via path finding
• If there is a path from
• And if there is a path from
• Then FAIL!
• How to find paths in graphs?
– DFS/BFS and modifications thereof
Example: CNF satisfiability
• This problem is in NP. Nondeterministic algorithm:
– Guess truth assignment
– Check assignment to see if it satisfies CNF formula

• Example:
(A¬B  ¬C )  (¬A  B)  (¬ B  D  F )  (F  ¬ D)
• Truth assignments:
ABCDEF
0 1 1 0 1 0
1 0 0 0 0 1
1 1 0 0 0 1
 ... (how many more?)

Checking phase: Θ(n)

3 CNF SAT (3 SAT)
• Not so easy anymore.
• Implication graph cannot be constructed
• No known polytime algorithm
• Is it NP?
– If someone gives you a solution how long does it
take to verify it?
– Make one pass through the formula and check
• This is an NP problem
• What is the 3-SAT problem?
• 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.
• What is the difference between 3SAT and
3CNF?
• A Boolean expression is in 3CNF if it is in
conjunctive normal form and each clause
contains at most 3 literals. 3SAT is defined as
the language consisting of those expressions in
3CNF that are satisfiable. 3SAT is NP-
complete, as there is a polynomial time
reduction from CNF-SAT to 3SAT.
A formula in CNF is valid iff all its disjunctions are valid. A disjunction is
valid iff for some atomic formula A the disjunction contains both A and ¬A as
literals (or the disjunction is empty.) Theorem: Satisfiability of formulas in
CNF is NP-complete. Theorem: Validity of formulas in DNF is NP-complete.

How do you determine if a formula is satisfiable?

A formula is satisfiable if at least one truth assignment for its variables makes
it true.

What is the CNF formula that is not satisfiable?

In contrast, the CNF formula a ∧ ¬a, consisting of two clauses of one literal,
is unsatisfiable, since for a=TRUE or a=FALSE it evaluates to TRUE ∧
¬TRUE (i.e., FALSE) or FALSE ∧ ¬FALSE (i.e., again FALSE), respectively.
• What is 3 CNF satisfiability?
• A boolean formula is in conjunctive normal
form, or CNF, if it is expressed as
conjunctions (by AND) of clauses, each of
which is the disjunction (by OR) of one or
more literals. A boolean formula is in 3-
conjunctive normal form, or 3-CNF-SAT, if
each clause has exactly three distinct literals.
Method
Review: P And NP Summary
• P = set of problems that can be solved in polynomial time
– Examples: Fractional Knapsack, …
• NP = set of problems for which a solution can be verified
in polynomial time
– Examples: Fractional Knapsack,…, Hamiltonian Cycle, CNF SAT,
3-CNF SAT
• Clearly P  NP
• Open question: Does P = NP?
– Most suspect not
– An August 2010 claim of proof that P ≠ NP, by Vinay Deolalikar,
researcher at HP Labs, Palo Alto, has flaws
Hamiltonian cycles
• Determining whether a directed graph has a
Hamiltonian cycle does not have a polynomial
time algorithm (yet!)
• However if someone was to give you a
sequence of vertices, determining whether or
not that sequence forms a Hamiltonian cycle
can be done in polynomial time
• Therefore Hamiltonian cycles are in NP
Reduction
• A problem R 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
• Intuitively: If R reduces in polynomial time to Q, R is
“no harder to solve” than Q
• Example: lcm(m, n) = m * n / gcd(m, n),
lcm(m,n) problem is reduced to gcd(m, n) problem
Polynomial Time Reductions
• The SAT problem is a circuit, so it is very useful and
interesting. Can we write a program to do X? This
and many other problems have been studied at
length.
• There are many mappings (called reductions) that
have been discovered that map one problem to the
other, so if we solve one we can solve the other.
• Moreover, these mappings are polynomial time
mappings.
Reducibility
• a problem Q can be reduced to another
problem Q’ if any instance of Q can be “easily
rephrased” as an instance of Q’, the solution
to which provides a solution to the instance of
Q
• Is a linear equation reducible to a quadratic
equation?
– Sure! Let coefficient of the square term be 0
NP - hard
• What are the hardest problems in NP?

• That notation means that L1 is reducible in

polynomial time to L2 .
• The less than symbol basically means that the
time taken to solve L1 is no worse that a
polynomial factor away from the time taken to
solve L2.
POLY-TIME REDUCIBILITY

A language A is polynomial time reducible to language B,

written A P B, if there is a polynomial time computable
function
f : Σ*  Σ*, where for every w,

w  A  f(w)  B

f is called a polynomial time reduction of A to B

NP-hard
• A problem (a language) is said to NP-hard if
every problem in NP can be poly time reduced
to it.
1. Polynomial Transformation ("  ")
• L1  L2 :
There is a polynomial time transformation
that transforms arbitrary instance of L1 to
some instance of L2.

• If L1  L2 then L2 is in P implies L1 is in P
(or L1 is not in P implies L2 is not in P)

• If L1  L2 and L2  L3 then L1  L3

Young CS 331 D&A of Algo. NP-Completeness 47

2. Focus on the class of NP – decision problems only. Many
intractable problems, when phrased as decision
problems, belong to this class.
3. L is NP-Complete
if (#1) L NP & (#2) for all other L'  NP, L'  L
• If an NP-complete problem can be solved in polynomial time then
all problems in NP can be solved in polynomial time.
• If a problem in NP cannot be solved in polynomial time then all
problems in NP-complete cannot be solved in polynomial time.
L • Note that an NP-complete problem is one of those hardest
problems in NP.
4. L is NP-Hard if
(#2 of NP-Complete) for all other L'  NP, L'  L
• Note that an NP-Hard problem is a problem which is as hard as an
NP 5. NP-Complete problem and it’s not necessary a decision problem.

Young CS 331 D&A of Algo. NP-Completeness 48

• So, if an NP-complete problem is in P then P=NP
• if P != NP then all NP-complete problems are in
NP-P

4. Question : How can we obtain the first NP-complete

problem L?

Cook Theorem : SATISFIABILITY is NP-

Complete. (The first NP-Complete problem)
Instance : Given a set of variables, U,
and a collection of clauses, C, over U.
Question : Is there a truth assignment
for U that satisfies all clauses in C?

Young CS 331 D&A of Algo. NP-Completeness 49

Example :
U = {x1, x2}
 
C1 = {(x1, ¬ x2), (¬ x1, x2)}
 
= (x1 OR ¬ x2) AND (¬ x1 OR x2)
 
if x1 = x2 = True  C1 = True
 
C2 = (x1, x2) (x1, ¬ x2) (¬ x1)  not satisfiable

“¬ xi ” = “not xi ” “OR” = “logical or ” “AND” = “logical and ”

This problem is also called “CNF-Satisfiability”

since the expression is in CNF – Conjunctive Normal
Form (the product of sums).
Young CS 331 D&A of Algo. NP-Completeness 50
• With the Cook Theorem, we have the
following property :

Lemma :
If L1 and L2 belong to NP,
L1 is NP-complete, and L1  L2
then L2 is NP-complete.
i.e. L1, L2 NP and for all other L' 
NP, L'  L1 and L1  L2  L'  L2

Young CS 331 D&A of Algo. NP-Completeness 51

NP Complete problems/languages
• Need to be in NP
• Need to be in NP-Hard

If both are satisfied then it is an NP complete problem

Reducibility is a transitive relation.

If we know a single problem in NP-Complete that helps when we are asked to

prove some other problem is NP-Complete

Assume problem P is NP Complete

All NP problems are reducible to this problem
Now given a different problem P’
If we show P reducible to P’
Then by transitivity all NP problems are reducible to P’
TSP
2
i = 23
2
1 1 3
4 1
3
5 4
4 2
1 2 2 2
2 1
1

1
• For each two cities, an integer cost is given to travel from one
of the two cities to the other. The salesperson wants to make
a minimum cost circuit visiting each city exactly once.
The clique problem is the
computational problem of
finding cliques (subsets of
vertices, all adjacent to each
other, also called complete
subgraphs) in a graph. It has
several different formulations
depending on which cliques,
and what information about the
cliques, should be found
Clique
A clique is a subgraph of a graph such that all the vertices in this subgraph are
connected with each other that is the subgraph is a complete graph. The Maximal
Clique Problem is to find the maximum sized clique of a given graph G, that is a
complete graph which is a subgraph of G and contains the maximum number of
vertices. This is an optimization problem. Correspondingly, the Clique Decision
Problem is to find if a clique of size k exists in the given graph or not.
4 – Clique Problem
K-Cliques
• A K-clique is a set of K nodes with all K(K-1)/2
possible edges between them

This graph contains a 4-clique

5-Clique
Hamiltonian Path
Map Coloring
P is a subset of NP
• Since it takes polynomial time to run the
program, just run the program and get a
solution
• But is NP a subset of P?
• No one knows if P = NP or not
• Solve for a million dollars!
– http://www.claymath.org/millennium-problems
– The Poincare conjecture is solved today
An example reduction
• CLIQUE problem
• A clique in an undirected graph is a subset of
vertices such that each pair is connected by an
edge
• We want to take a problem instance in 3-CNF
SAT and convert it to CLIQUE finding
Reducing 3CNF SAT to CLIQUE
• Given – A boolean formula in 3 CNF SAT
• Goal – Produce a graph (in polynomial time) such
that

• We will construct a graph where satisfying

formula with k clauses is equivalent to finding a k
vertex clique.
Decision problems versus optimization
problems
• Finding the maximum sized clique is an
optimization problem
• But we can reduce it to a series of decision
problems
– Can we find a clique of size 3 (why start at 3??)
– Can we find a clique of size 4
– Etc
• In general in our study of NP etc, we will focus
on decision problems
Proof that Clique Decision
problem is NP-Complete
• To prove that a problem is NP-Complete, we must show that it belongs to NP
and NP-Hard Classes. (Since NP-Complete problems are NP-Hard problems
which also belong to NP)
• The Clique Decision Problem belongs to NP – If a problem belongs to the NP
class, then it should have polynomial-time verifiability, that is given a
certificate, we should be able to verify in polynomial time if it is a solution to
the problem.
Proof that Clique Decision problem is NP-Complete

1. Certificate – Let the certificate be a set S consisting of nodes in the clique and S is a subgraph of G.
2. Verification – We have to check if there exists a clique of size k in the graph. Hence, verifying if number
of nodes in S equals k, takes O(1) time. Verifying whether each vertex has an out-degree of (k-1) takes
O(k2) time. (Since in a complete graph, each vertex is connected to every other vertex through an edge.
Hence the total number of edges in a complete graph = kC2 = k*(k-1)/2 ). Therefore, to check if the graph
formed by the k nodes in S is complete or not, it takes O(k2) = O(n2) time (since k<=n, where n is number
of vertices in G).
• Therefore, the Clique Decision Problem has polynomial time verifiability and hence belongs to the NP
Class.
• The Clique Decision Problem belongs to NP-Hard – A problem L belongs to NP-Hard if every NP
problem is reducible to L in polynomial time. Now, let the Clique Decision Problem by C. To prove that C
is NP-Hard, we take an already known NP-Hard problem, say S, and reduce it to C for a particular
instance. If this reduction can be done in polynomial time, then C is also an NP-Hard problem. The
Boolean Satisfiability Problem (S) is an NP-Complete problem as proved by the Cook’s theorem.
Therefore, every problem in NP can be reduced to S in polynomial time. Thus, if S is reducible to C in
polynomial time, every NP problem can be reduced to C in polynomial time, thereby proving C to be NP-
Hard.
Proof that the Boolean Satisfiability problem reduces to the Clique Decision
Problem

• Let the boolean expression be – F = (x1 v x2) ^ (x1‘ v x2‘) ^ (x1

v x3) where x1, x2, x3 are the variables, ‘^’ denotes logical
‘and’, ‘v’ denotes logical ‘or’ and x’ denotes the complement
of x. Let the expression within each parentheses be a clause.
Hence we have three clauses – C1, C2 and C3. Consider the
vertices as – <x1, 1>; <x2, 1>; <x1’, 2>; <x2’, 2>; <x1, 3>; <x3,
3> where the second term in each vertex denotes the clause
number they belong to. We connect these vertices such that –

• No two vertices belonging to the same clause are connected.

• No variable is connected to its complement.
Proof that the Boolean Satisfiability problem reduces to
the Clique Decision Problem
Proof that the Boolean Satisfiability problem
reduces to the Clique Decision Problem
• Thus, the graph G (V, E) is constructed such that – V = { <a, i> | a belongs to Ci }
and E = { ( <a, i>, <b, j> ) | i is not equal to j ; b is not equal to a’ } Consider the
subgraph of G with the vertices <x2, 1>; <x1’, 2>; <x3, 3>. It forms a clique of size 3
(Depicted by dotted line in above figure) . Corresponding to this, for the
assignment – <x1, x2, x3> = <0, 1, 1> F evaluates to true. Therefore, if we have k
clauses in our satisfiability expression, we get a max clique of size k and for the
corresponding assignment of values, the satisfiability expression evaluates to true.
Hence, for a particular instance, the satisfiability problem is reduced to the clique
decision problem.

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

Conclusion
• The Clique Decision Problem is NP and NP-Hard. Therefore, the Clique decision
problem is NP-Complete.
Proof that traveling salesman
problem is NP Hard
• https://www.geeksforgeeks.org/proof-that-tr
aveling-salesman-problem-is-np-hard/