Tractable

and
Intractable

UNIT -VI
 Tractability of a problem

 Tractability of a problem refers to difficulty level of a

problem. Difficulty in terms of amount of time it
takes to solve that problem.
 Tractability is related with the time complexity of a
solution algorithm.
Some common functions, ordered by how fast
they grow.
 Continue..

 Polynomial functions: Any function that is O(nk),

for some constant k.
 E.g. O(1), O(log n), O(n), O(n × log n), O(n2), O(n3)
 Exponential functions: The remaining functions.
 E.g. O(2n), O(n!), O(nn)
 Tractable

 Problems that can be solved in reasonable time called

Tractable. OR
 A problem that is solvable by a polynomial-time algorithm.
 Here are examples of tractable problems (ones with known
polynomial-time algorithms):
1. Searching an unordered list
2. Searching an ordered list
3. Sorting a list
4. Multiplication of integers
5. Finding a minimum spanning tree in a graph
 Intractable

1. Problems that “can be” solved but the amount of time it

takes to solve is too large.
2. A problem that cannot be solved by a polynomial-time
algorithm.
3. Can be solved in reasonable time only for small inputs.
Or, can not be solved at all.
4. As their input grows large, we are unable to solve them in
reasonable time.
o Eg: TSP
 Classification of Problems

 Can be classified in various categories based on their degree

of difficulty, e.g.,
P

 NP

 NP-complete

 NP-hard
 Class P Problems

 P is the set of all decision problems solvable by

deterministic algorithms in polynomial time.

 Polynomial time algorithms

o Decision problem
o Deterministic algorithm
o Sequential execution, no parallel processing

 E.g. Binary tree search –

o Time complexity O(log n)
o Only one node comparison at a time
o No parallel comparisons
 Class NP

 Non deterministically polynomial(NP) time

algorithms
 Decision problems
 Nondeterministic algorithm
 Parallel computations
 Polynomial time complexity
 E.g. travelling salesman problem,O(n2 2n)
 Class NP

 NP is the set of all decision problems solvable by

nondeterministic algorithms in polynomial time.
OR
 Set of all problems which can be solved by a non-
deterministic Turing machine in polynomial time.
OR
 The problems whose solution can be verified in
polynomial time on a deterministic machine.
 If we are given a certificate of a solution, we can verify
that the certificate is correct in polynomial time in the
size of input to the problem(eg TSP )
 Continue..

 Nondeterministic algorithms: are allowed to

contain operations whose outcomes are limited to a
given set of possibilities instead of being uniquely
defined.

 Machine capable of executing a nondeterministic

algorithm is called a nondeterministic machine
 Relation between P and NP Problems

 An unsolved problem in computer science is: Is P =

NP or is P  NP?

NP

Any problem that can be solved by deterministic m/c

in polynomial time can also be solved by non-
deterministic m/c in polynomial time.
 Some NP Complete Problems

 Graph Coloring
 TSP

 Bin Packing

 Knapsack

 Subset Sum

 Minesweeper Constraints

 Many More
Polynomial Time Problems

EXAMPLES
 Minimum Spanning Tree

 Undirected weighted graph,G = (V, E)

 V: set of vertices

 E:set of edges

 w(u,v):weight of edge connecting vertices u and v

 Objective:
 Find acyclic subset of edges that covers all vertices and whose
total weight is minimized
 Known as Minimum Spanning Tree (MST)

 Total weight, W= ∑ of weights of all edges belonging to MST

 Application (MST)

 Example:
 Designing an electronic circuit with a set of‘n’ pins and wires

 Objective: Connecting all the ‘n’pins

 Minimum wires required: n–1

 Aim: To choose the best circuit among all

possibilities that incurs minimum expenses if wires
are of different costs
(example) Graph ‘G’ and its MST ‘T’
 Kruskal’s Algorithm

 Finds a minimum spanning tree ‘T’ for a connected

weighted graph ‘G’
 E:Set of all edges in G in sorted order of their weights
 Time Complexity :O(E log E)
 While (T has less than ‘n –1’ edges) && E is not
empty
1. Choose an edge (v, w) from E of lowest cost
2. Delete (v,w) from E
3. Add(v, w)to T, if it doesn’t create a cycle
4. Else discard(v, w)
 Manchester
40

30
Liverpool
Sheffield
110
70
40

Shrewsbury 50
50
80 Nottingham
B/ham

Aberystwyth 110 70 100

120 90

50 Oxford
Bristol

Cardiff 80
70

Southampton
NP Problems

EXAMPLE
 Travelling Salesman Problem

 Task: Given a list of cities and the distances between

each pair of cities, what is the shortest possible route
that visits each city exactly once and returns to the
origin city?
 It is an NP problem
 Problem:
 Undirected weighted graph, such that cities are the graph's
vertices, paths are the graph's edges, and a path's distance is
the edge's length.
 It is a minimization problem starting and finishing at a
specified vertex after having visited each vertex exactly once.
 Continue..

 The original formulation:

 Instance: A weighted graph G

 Question: Find a minimum-weight Cycle in G.

 The yes-no formulation:

 Instance: A weighted graph G and a real number d

 Question: Does G have a Hamiltonian cycle of weight <=

d?
Example
 Continue..

 It is not difficult to find solution to TSP in a small

graph like this but as the size of the graph grows the
time-demand appears to scale very badly and it is
strongly believed that there are no polynomial time
algorithms for this problem.
 there is no algorithms which solve this problem in
polynomial time.
 NP complete

 NP-complete problems are the hardest problems in NP set.

 Definition: A problem B is NP-complete if:

(1) B  NP
(2) A p B for all A  NP
 If B satisfies only property (2) we say that B is NP-hard

 An equivalent but casual definition: A problem R is NP-

complete if R is the "most difficult" of all NP problems.
 Reductions
 Reduction is a way of saying that one problem is
“easier” than another.
 We say that problem A is easier than problem B,
(i.e., we write “A  B”)
if we can solve A using the algorithm that solves B.
 Idea: transform the inputs of A to inputs of B

yes
  yes
f Problem B no
no
Problem A
 Implications of Reduction

yes
  yes
f Problem B no
no
Problem A

- If A p B and B  P, then A  P
- if A p B and A  P, then B  P
 Importance

 Learning reduction in general is very important.

 For example, if we have library functions to solve certain
problem and if we can reduce a new problem to one of
the solved problems, we save a lot of time.
 Consider the example of a problem where we have to find
minimum product path in a given directed graph where
product of path is multiplication of weights of edges
along the path. If we have code for Dijkstra’s algorithm to
find shortest path, we can take log of all weights and use
Dijkstra’s algorithm to find the minimum product path
rather than writing a fresh code for this new problem.
 Proving NP-Completeness In Practice

 Prove that the problem B is in NP

 A randomly generated string can be checked in polynomial
time to determine if it represents a solution

 Show that one known NP-Complete problem can

be transformed to B in polynomial time
 No need to check that all NP-Complete problems are reducible
to B
 First NP complete problem?

 There must be some first NP-Complete problem

proved by definition of NP-Complete problems.

 SAT (Boolean satisfiability Problem) is the first NP-

Complete problem proved by Cook.

 That is, any problem in NP can be reduced in

polynomial time by a deterministic TM to the
problem of determining whether a Boolean formula
is satisfiable.
NP –complete Problems
Satisfiablity

EXAMPLE
 [Link] (SAT) problem

 Determining: If there exists an interpretation that

satisfies a given Boolean formula.
 Determining: If the variables of a given Boolean
formula can be assigned in such a way that the
formula evaluates to TRUE.
 If no such assignments exist, the function expressed
by the formula is identically FALSE for all possible
variable assignments.
 In this latter case, it is called unsatisfiable, otherwise
satisfiable.
 Example:

 Consider the Boolean expression: “a AND NOT b”

 Let,a=TRUE and b=FALSE
 Expression becomes(a AND NOT b)=TRUE
 Hence it is satisfiable.

 Consider the Boolean expression: "a AND NOT a"

 Let, a=TRUE, the expression becomes FALSE
 Let, a=FALSE, the expression becomes FALSE
 Hence it is unsatisfiable
 Normal Forms of Boolean Expressions

 Disjunctive normal form:(DNF)

if a boolean expression can be expressed as the sum
(OR) of products (AND).
 This can be written as:
 A1 OR A2 OR A3 OR...An
 Where each Ai is expressed as T1 AND T2 AND......AND Tm

 where each Ti is either a simple variable, or the negation

(NOT) of a simple variable.
 Each of the terms Ai is called a minterm.
 CNF

 Conjunctive Normal Form: if a boolean

expression can be expressed as the product (AND) of
sums (OR).
 This can be written as:
 O1 AND O2 AND O3 AND ...On
 where each Oi is expressed as T1 OR T2 OR...OR Tm

 where each Ti is either a simple variable, or the negation

(NOT) of a simple variable.
 Each of the terms Oi is called a max term.
 Continue..

 It is difficult to prove NP completeness of any NP

problem
 Convert every NP problem ‘P’ to satisfiability
problem to prove it is NP complete .
 NP Complete problems
 Travelling Salesman Problem
 Node cover problem
 Hamiltonian Circuit problem
 CSAT: Is a boolean expression in CNF satisfiable
 [Link] cover Decision Problem

 It is a subset of vertices that touch all the edges in an

undirected graph
 Node cover for this graph is:{1,6}
 which has size 6 - 4 = 2.
 Continue..

 If node cover C of graph G with ‘n’ vertices has no

removable vertices from C then the minimum node
cover is C.
 Else, for each removable vertex v of C, find the
number ρ(C−{v}) of removable vertices of the vertex
cover C−{v}.
 Repeat until the vertex cover has no removable
vertices.
 Time complexity =O(n5)
 This problem can be proven as NP complete by
obtaining a polynomial time reduction of SAT
 3. Hamiltonian Circuit Problem

 Hamiltonian path is a path in an undirected or

directed graph that visits each vertex exactly once.
 A Hamiltonian cycle/ circuit is a Hamiltonian path
that is a cycle.
 Determining whether such paths and cycles exist in
graphs is the Hamiltonian path problem.
 This problem is NP-complete.
Example
E.g.: Hamiltonian Cycle

hamiltonian

not
hamiltonian
 Problem of Independent Sets

 An independent set or stable set is a set of vertices in a graph, no

two of which are adjacent.
 It is a set ’v’ of vertices such that for every two vertices in ’v’,
there is no edge connecting the two.
 Equivalently, each edge in the graph has at most one endpoint in
’v’.
 The size of an independent set is the number of vertices it
contains.
 In general

 To prove NP Completeness
 Prove that the problem can be solved in polynomial time
by non deterministic way
 Then try to show that the problem can be expressed as
satisfiability problem
 Now, satisfiability problem is already proven as NP
complete as the 1st problem
 So given such problem also becomes NP complete

 Else it is NP hard
Relation between different classes of problems