Intractable 

Problems
Intractable Problems
The Classes P and NP
Mohamed M. El Wakil
Mohamed M. El Wakil
mohamed@elwakil.net

1
 Agenda
1. What is a problem?
2. Decidable or not?
Decidable or not?
3. The P class
4. The NP Class
5
5. The NP‐Complete
The NP Complete class
class

2
 What is a problem?
What is a problem?
• A problem is a question to be answered.
– What is the value of X/Y?
• A problem usually has parameters.
p y p
– X, and Y
• A
A decision problem, is a version
decision problem is a version of the 
of the
problem with only two possible answers: Yes 
or No!
or No!
– Given two numbers X, and Y, does Y evenly divide 
X?
• An instance: a specific problem instance
– Does 3 evenly divide 6?
3
 Decidable or not?
Decidable or not?
• A decidable problem, is a problem that could 
be solved using a computer.

• A
An undecidable problem, is a problem that 
d id bl bl i bl th t
can never be solved using a computer, neither 
now or in the future.

• Only decidable problems!
4
 Classification
• We need to classify problems in terms of their 
p y
computability.

• Three classes:
Th l
– P class
– NP Class
– NP‐Complete class
NP‐Complete class

5
 P class wrt Computers
P class, wrt
• Problems with at least one algorithm that 
solves the problem in polynomial time wrt
l h bl i l i l i to 
the input size.

• Polynomial time 
Polynomial time
– The number of steps needed relates polynomially 
to the size of the input
to the size of the input. 
– O(n2), O(n9), O(nc), where c is a constant.
but NOT O(n!) O(2n), when n is the size of the 
– but NOT O(n!), O(2 ) when n is the size of the
input.

6
 P class wrt Turing Machines
P class, wrt Turing Machines
• Problems solvable in polynomial time using a 
D t
Deterministic  Turing Machine  (DTM) belong to 
i i ti T i M hi (DTM) b l t
the class P.

• Polynomial time 
– The number of moves needed relates polynomially to 
the size of the input. 
• n2, 17n3, 9n4, but NOT 2n
• DTM
– A Turing machine with a tape, head, transition 
function, and a set of states.

7
 P Problem (MWST)
P Problem (MWST)
• Minimum Weight Spanning Tree 
– Given a weighted graph G, find the minimum 
g g p ,
weight spanning tree. 

– In other words, convert the given graph into a 
tree that includes all the nodes of the original
tree, that includes all the nodes of the original 
graph, and minimizes the summation of weights of 
the edges in the resulting tree
the edges in the resulting tree.

8
 MWST Example
Problem Instance

Source: http://en.wikipedia.org/wiki/Kruskal's_algorithm
9
 Kruskal'ss algorithm
Kruskal
• The MWST problem belongs to the P class of 
h S bl b l h l f
problems, since there is an algorithm that solves  
it i
it in polynomial time. 
l i l ti
• Kruskal's algorithm O(n2)
– Create a forest F (a set of trees), where each vertex in 
the graph is a separate tree 
– Create a set S containing all the edges in the graph 
– While S is nonempty 
• Remove an edge with minimum weight from S 
• If that edge connects two different trees, then add it to the 
forest, combining two trees into a single tree
forest, combining two trees into a single tree 
• Otherwise discard that edge 
10
 MWST Example
Possible Solution

Source: http://en.wikipedia.org/wiki/Kruskal's_algorithm
11
 NP class wrt Turing Machines
NP class, wrt Turing Machines
• Problems solvable in polynomial time using a 
g (
Non Deterministic Turing Machine  (NDTM) )
belong to the class NP.

– NDTM
• A DTM, with two stages of processing: guessing, and 
h f d
checking. 

12
Non Deterministic Turing Machine
Non‐Deterministic Turing Machine
• Guessing:
G i
– Guess a solution, and then write it down to the tape.

– Checking:
• Evaluate the guess to decide whether it solves the problem 
or not.
• The
The number of guessed solutions, can be either 
number of guessed solutions can be either
polynomial or exponential.
• If the number of guessed solutions is polynomial, 
If th b f d l ti i l i l
then, the NDTM is equivalent to a DTM.

13
 NP class wrt Computers
NP class, wrt
• Problems that can be solved within an 
p
exponential time wrt the input size. 
p

• Thi
This includes problems that can be solved in 
i l d bl h b l di
polynomial time.

14
 Important
• A DTM is a NDTM that has a polynomial 
g
number of guesses.

• A
According to the definition of NP, the MWST 
di h d fi i i f NP h MWST
problem is an NP problem.

15
 NP Problem Example
Travelling Salesman Problem (TSP)

Given a number of cities and the costs of traveling from any city to any other 
city, what is the cheapest round‐trip route that visits each city exactly once 
and then returns to the starting city?
and then returns to the starting city?

Source: http://en wikipedia org/wiki/Traveling salesman problem

16
 Solving the TSP
Solving the TSP
• There is no one single algorithm  that solves 
p p y
this problem in polynomial time /

• Th
The only way, is to enumerate all possible 
l i ll ibl
itineraries and checking them one‐by‐one.

• For n cities, there are n! routes
F iti th ! t

17
 Polynomial Time Reduction
Polynomial Time Reduction
• A problem P1, is polynomially reducible to 
problem P2, if there is a process
p p that takes an 
instance of P1 as an input, and outputs a 
corresponding instance of P2 in polynomial
corresponding instance of P2 in polynomial 
time. 

– P1: a * b
– P2: ((a+b)2 – a2 – b2)/2

18
 NP Complete Class
NP‐Complete Class
• A problem P is NP‐Complete If:
– P is in NP
– For every problem L in NP, there is a polynomial 
time reduction from L to P
time reduction from L to P.

• If
If P1 is NP‐Complete, and there is polynomial 
P1 i NP C l t d th i l i l
time reduction from P1 to P2, then P2 is NP‐
Complete.

19
 NP‐complete 
NP l t
problems family
problems family 
tree

20
 The NP World
The NP World

Source: http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP

21
Intractable Problems
Intractable Problems
The Classes P and NP
Mohamed M. El Wakil
Mohamed M. El Wakil
mohamed@elwakil.net

22