Problem Classification

1,
introduction

111
e computational problems are hard. We rack our brains to find efficient algorithms for
~,;ng them, but time and time again we fail. It would be nice if we could prove that finding an
Ill1
efficient algorithm is impossible in such cases. For then we could take comfort from the fact that
no efficient algorithm exists for this problem. Unfortunately, such proofs are typically ev~n
nafder to come by.

~till, all is not frustration. The proofs involve a concept known as NP-Completeness. While
~owing that a problem is NP-Complete is admittedly not the same as proving that an efficient
algorithm for the problem is impossible, showing that a problem L is NP-Complete says that,
although we have been unable to find an efficient algorithm for L, neither has any computer
iCientist who has ever lived!

Classification of Problems
Problem

/~
Unsolved Solved

Polyno~ ~ m i a l time
(tractable) (NP hard) (intractable)

. Oeterm~ ~rmlnlstic (NP)

8-1
 ()~
8-2 / VIIIOlt Design and Analysis of Algorithm

2. Non-Deterministic Algorithms
.
t· d But some algorithms conta·
.
Generally, . are
the result of every operation. is umquelY dde bine . . sets 0mf
· limited to specific
operations whose outcomes are nol umquely define ut

possibilities.
For example, consider a function Choice (s).
Choice (s) arbi1rarily chooses one of the elements of sel S. If choice( ) chooses an element that
leads 10 successful completion, then 1he algorithm 1ennina1es successfully.

Definition
Non-deterministic algorithm 1erminales unsuccessfully if and only if there exists no set of

choices leading to successful completion.

A machine capable of executing a non-deterministic algorithm is called a non-de1erminis1ic

machine.
Example
Write a non-deterministic algorithm which searches an element x in a given set of elements.

A[l:n], n 2: 1.

Solution
To determine an indexj such that,

A[j) = x or j = O if x e A
Algorithm Search x(x)
{
j. := Choice(l,n) ,•
if A[j) = X then
{
write [j); Success()•
// Signals successful' completion
write (0); Failure(),· // Signals unsuccessful completion

Th
In the above problem,•Failure ( ) and Success () are used to si I . ji.
ey are not same as return• statement. gna computation of the algorithm.
 Problem Classification

deterministic algorithm can be tl1 k everal copies of

non· . oug11t as the algorithm that ma es s
A for each choice. The first • all other
-iself, one . . · copy to reach successful completion, ternunates ,
~utations. If copy teach~s failure completion, then only that copy is terminated. If lbere JS ~o
c1toict (or sequences of choices) leading to successful termination, the algorithm terminates with
t ''unsuccessful ternunation 11
•
outl'u

[)8flnitton
red
'[be ume
requi by a non-deterministic algorithm performing on any given input is tbe
st
nunirnum number of eps needed to reach a successful completion if there exists a sequence of
chOices leading to such a completion. In case successful completion is not possible, then the time
required is 0(1). A non-deterministic algorithm is of complexity O(f(n)) if for all inputs of size
n, n 2: no, that results in successful completion, the time required is at most c f(n) for some
constants O and integer 11o.
Examples

1. Non Deterministic Algorithm For satisfiability problem

Algorithm Satisfiability(E,n)
//The expression E is satisfiability problem containing n clauses in
the form of X [i] 's
{
For i=l to n do
X[i]=choice(True,False);
If (E (X[l], X [2], .......... , X [n]=True) then
Success();
Else
Failure();

Time Complexity=O(n)
2. Non Deterministic algorithm to search an element in array
Algorithm Search(A,n,x) , th element to search
//A is the array of n elements & x is e
{
Y=Choice(A,1,n)
If (A(j]=x)then
Success();
Else
Failure O;

Time Complexity =O( 1)

 8-4 / rJ
v111in Design and Analysis of Algorithm·

· ·d d as decision problem - To de .
Example ternune
[Oil Knapsack) Oil Knapsack problem can be cons• ere
whether there is a Oil assignment of values to x,, I :;; i:;; n, sue~ ~at L p; x ; 2: r and L w, X; :;; m,
where r is given number and p,, w, are non negative numbers giving profits and weight of object

the decision problem cannot be solved in detenninistic polynomial time then even
iIfrespectively.

optimization knapsack problem cannot be solved in poJynonrial time.

8
Examples
.. 1. Let A[i], 1 S i S n, be an unsorted array of positive integers. Write
deterministic algorithm to sort the elements of A into non decreasing order. non-

Solution
Given an array A[l : n].
We use an auxiliary array B[l : n].
Algorithm NSort(A,n) integers.
//Algorithm to sort n positive
{
for(i=l to . n) do
B [_il := O; //Initialize
f or(i:=l ton) do .
{ //Assign each A[i]
j := Choice (l,n);
//position in B
:= *
if(B[j]
B[j] 0) then Failure();
A[i];
}
//Verify Order
fo~(i:=l to (n-1) do
!f B[i) > B[i+l] th e Failure {);
Write (B[l:n]);
Success();
}

Write a non-deterministic polynomial time a1gonlbm for knapsack decision

.. 2. problem, .

Solution
To assign values to x[i] ' 1 -< 1. S n such th A successful
· · is
temnnatton • possible iff the answer to the dee· . g
resultin .
the problem
at1s1on profit is
. at least r
is yes. .
r

()"J \
Problem Classification
UIIIOII 8·5
·thm Knapsack(p,w,n ' m, r ,X )
J'."l·
~1g 0 . l is array of profits
;/P[~l is array of weights
I/w[:i.
(
W"' ,
0. p: ==0
f~r (i"'l to n) do
{
x(i] := Choice (0, 1);
//Assign value to x[i]
W :=Wt X(i] * W(i);
p := P + x[i) * p[i);

if ( (W > m) or (p . < r) ) then •

I /Checks· whether assignment
//is feasible
failure () ;
else Success () ;

t3. Write 8 non-deterministic algorithm for Max Clique decision problem.

Solution
Algorithm NMaxClique(G,n,k)
//Given a -graph G on . n vertices
I /To check existence of · k_:clique in G
{ '

S: =q,; I IS is an empty set

for(i:=l to k} do
{
t:=Choice(l,n);
if tes then Failure();
S:=S U {t} //Add t to S.
//Form set S of . size k.
for(all pairs(i,j) where i,je~ ~nd i*j) do
{
if(i,j) is not an edge of G
then Failure(); //Checks if Sis complete graph

Success () ;
}

~4.
complexity?
.
Write a non-cleterminlstlc algorithm
.
to solve knapsack problem. What is its, ... time
'
,'' '
--,
1\
Solution cr0ct;201'e'.~1~ t~•::t~,, "' I

kon-deterministic Algorithm for knapsack problem a

. Write non-deterministic -
algorithm to solve
knaP&ack problem.
8-6 / VI~/.:" Design and Analysis of Algor ithm

n m r , x)
Alg orit hm DKP (p, w, ' '
{
. p ·=
. 0; r = O;
w := 0 ,
for i = 1 to n d o
{
x [i] c h oic e(l, n)~ .
=
W = W + X [i] * W ( ~]:
p .., p + X [ i ) * p ( J.]'

} < r) then
if(w > m) or(P
fail ure ();
else suc ces s(); t 0 f O positive integers.
} . . . al rithm to sort se
Write non-deternumst1c go
~5
Solution
Alg orit hm Nso rt(A ,n)
//so rt 'n' pos itiv e inte ger
{
for i:= l ton do
B[i] :=0; //In itia te
for i:=1 ton do
{
J:=c hoi ce(l ,n);
if(B [j) !=:O) then fail ure ();
B [ j] : =A ( i] ;
}
for i:=1 ton do; //ve rify ord er
if(b (i] > B[i+ l]) then fail ure ();
Wri te (B[ l:n] );
Suc cess ();
}
inj being assi gned any one of the integers
The assignment statementj:= choice(l,n) could result
this choi ce is to be mad e. The failure() and
in the range [l,n]. There is no rule specifying how
algorithm..
success() signals are used to define a computation of the
41 for 4 num bers only 1 will give the
The non-deterministic sorting will have 4 cases, i.e.,
solution.
Tim e com plex ity for this algo rithm is n!.
 ( },; \ 81
u1s1011 -
Problem Classification

preliminary Issues
3,

input Size what we mean

3,1
of input size as
need to be more precise about running time. Instead of the informal notion
of
we .,,ber of 'items ' that form input, we define input size'n' of a problem to be the number
~~··
. sed to encode an input instan ce. Each character uses a constant number of bits and •
each
bttS U • •
r M > 0 1s represented with at most c log M bits• c-constant· In particular, we disallow
jntege .
unarY encod ing, where an mtege r M is represented with M 1's.

[tt N = the number of items in input,

n = the riumber of bits to encode the input.
M for some constant
Thus, if M is the largest integer in an input then N + log M $ n ~ c N log
c>O,
terms of the number of
' Therefore, any "reasonable" algorithm that runs in polynomial time in
bits.
input items will also run in polynomial time in terms of the number of input

3.2 Advantages: Polynomial

We know that for the problems such as text processing or sorting or matri
x multiplication have
time complexity of polynomial order (or of order O(log n)).
ion and composition.
Moreover, the class of polynomials is closed under addition, multiplicat
That is, if p(n) and q(n) are polynomials, then so are p(n) + q(n), p(n)
• q(n) and p(q(n)). Thus,
new polynomial time
we can combine or compose polynomial time algorithms to. construct
algorithms.

3.3 Decision Problems and Optimization. Problems

Definitions
is called a decision
Decision problem: Any problem for which the ans~er is either zero or one
Problem. An algorithm for a decision problem is called decision algorithm.
 Des ign and Ana lysis of Algo rithm

valu e of
izat ion pro blem : A pro blem that involves iden tific ation of an opt imu m
Optim
mizatio n pro blem.
obje ctiv e (or cos t) fun ctio n is call ed an opti
n pro blems.
For example, eac h of the following is decisio
ear as a sub stri ng of T ?
• Giv en a stri ng T and a string P, doe s p app
sam e num ber of elem ents ?
• Giv en two sets San d T, do San d T con tain
s G have a
Giv en a grap h G with inte ger wei ght for its edg es, and an inte ger k, doe
•
min imu m spa nnin g tree of wei ght at mos t k?
into a
, the last pro blem illu stra tes how we can ofte n tum an opt imi zati o~ pro blem
In fact mia l time
pro blem has an algo rith m with pol yno
dec isio n problem. Thi s recasted dec isio n
onl y if the corr esp ond ing opti miz atio n pro blem has . In oth er cas es, we can
com plex ity if any
then
mak e the stat eme nt that if the dec isio n pro blem can not be solv ed in pol yno mia l tim e
atle ast
not dither.
the corresponding optimization pro blem can

Example
grap h of a gra ph G(V ,E) is a cliq ue. The
.. 1. (Maximum clique): A maximal com plet e sub
ices in it.
size of clique is defined as the num ber of vert
If G is a graph give n then cliq ue is G 1•

v,

Size of cliq ue= 3.

atio n pro blem - To dete rmi ne the size
~:: ::.: :~~ ~~ fur [Link] ble m is an opti miz

Solution
· n problem - To dete rmi n
as a dee·is1o h th G h as a
Thi s pro blem can be restated and solv ed e w e er
cliq ue of size at leas t k.
. .
algo rith m for the a b ove deC1s1o
Let Cliq ue (G, k) be dete rmi nist ic dec isio n n pro blem .
r
{?'> \ 89
u1s1011 •
Problem Classification

•'(G)I::::: o then Clique (G, k) is executed fork == -

1r 1v n, n 1, n - 2, ... , l until the output of Clique
1 ll,,):::::l ,
i (0• r.
' ct·que (G, k)) = f(n) then the siz f .
can be found in time~ n * f( n) ·
If O( 1
• e O max clique
Max clique optiinization prob\ .
and on 1Y1· f the max
~ence, .
em can be solved in polynomial time 1f
e decision problem can be solved in poly . .
cliqu nomial time.

...- ... '

4. The Class P, NP, NP-ha rd, NP-Co mplet e Problems ( 1 ',~
- Apr.
- ----' ""'' "'
2017- 2M "'
,,
Define P and NP class
4.1 p.c1ass problems.

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 or superpolynomial.
formally, an algorithm is polynomial time algorithm, if there exists a polynomial p(n)such that
thealgorithm can solve any instance of size n in a time O(p(n)).

Problem requiring U(n50) time to _solve are essentially intractable for large n; Most known
polynomial time algorithm run in time O(nk) for fairly low value of k_-
,
The advantages in considering the class of polynomial-time algorithms is that all
reasonable deterministic single processor model of computation can be simulated on each
other with at most a polynomial slow-d

4.2 NP-Class

The class NP consists of those problems that are verifiable in polynomial time. NP is the class of
decision problems for which it is easy to check the correctness of a claimed answer, with the aid
of a little extra information. Hence, we aren' t asking for a way to find a solution, but only to
verify that an alleged solution really is ·correct.
Every problem in this class can be solved in exponential time using exhaustive search.
 )
8-10 / v1i,;11 Design and Analysis of Algorithm

P versus NP . . . lynornial time algorithm is als 0

Every decision problem that is solvable by a detemunisuc po
solvable by a polynomial
. . . algorithm,
time non-deterministic • ·t",.,.,S whereas all problems in NP
1
All problems m P can be solved with polynonual ume a gon '"" , -

P are intractable.
It is not known whether p = NP. However, many problems are known in NP .with the propeny

that if they belong to P, then it can be proved that P = NP.

If Pf NP, there are problems in NP that are neither in P nor in NP-Complete.
The problem belongs to class P if it's easy to fmd 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.
r""l!Nc!e / Every deterministic algorithm is a spec"i case of non-deterministic algorithm with number of
choices equal to 1. : . P~ NP.
Obvious question now is NP !;:; P?
i.e., is there a non-deterministic algorithm for which there is no deterministic algorithm? If
P-N~ •

Definition 2
Let L1 and L2 be problems. Problem L1 reduces to L2 (Notation oc . . .
solve L by a deterministic polynoffila .
. algonthm
. tune . L1 L2) 1ff there 1s a way to
1 using a dete . . . al .
L, in polynomial
1 time. nmrusllc gorithm that solves

Lemma: oc is a transitive relation

Let L1 oc L2 and Li oc L3.
:. L3 has polynomial time algorithm
⇒ L2 has polynomial time algorithm.
L2 has polynomial time algorithm
⇒ L1 has polynomial time algorithm.
:. If L3 has polynomial time algorithm then LI has polyn ·a1 .
.-. L, "'L Ollll tune algorithm.
3

Therefore, ex is a transitive relation.

f
(.7', \
Problem Classification v1s1on 8-11
tlnition
oe A problem L is NP-h~rd iff sat' -r . .
,
1 . . 1ab1ltty reduce . t L
( l::;
· Aproblem L 1s NP-complete iff L . . s O ·
ii- is NP- hard and L E NP.

NP-Completeness
4. 3

notion of non-deterministic accept ..

fbe f mal computer that ance of a decision problem is indeed strange, as there is
0o o1 can execute h .
· ·stically simulate -d . . . sue algorithm efficiently. Certainly, we can
deternum non eternunistic 1 .· h .
utcomes to the choose() statements. But th' a·gout .m by trymg out, one by one, all possible
o Is simu1ation would run in exponential time.
Infact, there are hundreds of problems in cl N .
. . ass P, for which most computer scientists strongly
t,elieve there 1s no conventional method for solvi'ng th • . .
em m po1ynomta1time.
Thus, useful~ess of class NP is that it formally captures a host of problems that many believe to
be computationally difficult. This notion of hardness is based on the concept of polynomial time
reducibility. · '

4.4 Polynomial Time Reducibility and· NP-hardness

A problem L is NP-hard if every other problem M in NP is polynomial time reducible to L.

Thus, an NP-complete problem is, in a very formal sense, one of the hardest problems in NP, as
far as polynomial time computability is concerned. For, if anyone ever shows that an NP-
complete problem L is solvable in polynomial time, then that immediately implies that every
other problem in entire class. NP is solvable in polynomial time. In other words, if anyone finds
adeterministic polynomial time algorithm for even one NP.,complete problem then P = NP.
NP complete

NP
hard

hi between P, NP, NP-complete and NP-hard problems

Figure 8.1: Commonly believed relations P
 /4
8·12 / u1i1on Design and Analysis of Algorithm
· L · NP such that if LE P then it
10
S. Cook formulated the question: Is there any single problem
th
would imply that P = NP? He answered this question in following eorem.

Theorem: [Cook) Satlsflablllty Is In p If and only If p == NP.

Example t
(Halting problem) The halting problem is to determine for an arbitrary determiniS ic algorithm A
and an input I whether algorithm A with input I ever terminates or enters an mfirute loop.

There is no algorithm of any complexity to solve this problem. Hence it is not NP·

Let X be a prepositional formula with n variables.

If A tries out all 2" possible truth values of n variables, we can verify whether Xis satisfiable. If
it is then A stops, otherwise A enters infinite loop.
:. A halts on input X if and only if Xis satisfiable.
:. If we have a polynomial time algorithm for halting problem, then we can solve the
satisfiability problem in polynomial time. ·
Hence, the halting problem is an NP-hard problem, but it does not belong to class NP.

Definition
Two problems L1 and L2 are said to be polynomially equivalent if and only if L 1 oc L2 and L2 oc
Ll·
To bshow that a problem L2 is NP-hard, it is enough to show that Li oc Li for some NP hard
pro 1emL1•
~e::: tbat an NP-hard decision problem is NP-complete, we have to produce a non- Cook's

5. Cook's Theorem

In 1971, Stephen Cook published a a er in .

Complexity of Theorem Proving Proced:..~. computal!onal complexity theory - ''The

The same theorem was independently proved b L . .

sometimes called Cook-Levin theorem. y eomtl Levm at about the same time; it is
 ? \ 8-13
{, 01111
Problem C/assificaffon
VIII

oefinltion of NP- Problems

ot~er
'11 . problem is in NP if a non d . . . · olynornial
decision - etermm1sttc Turing machine can solve it. tn P
~
uoie· .
all that an mstanc_e of the_ Boolean satisfiability problem is a Boolean expression that
ieeJllb1nes
. Boolean vanables using BoO1 . . ·r h is
ean operators. An expression 1s satisfiable 1 t ere
co ·gnment of truth values to the v · bl . ·
sotne assl aria es that makes the entire expression true.
s,a,ement of Cook's Theorem
s,usfiability problem is in P if and only if p = NP.

prqo!
1bC statement of the theorem can be restated as satisfiability problem is NP-Complete. The
BoOlean satisfiability problem is in NP because a non-deterministic Turing machine guess an
assignment of truth values to the variables, determine the value of the expression under that
assignment and accept if the assignment makes the entire expression true.

Now suppose that a problem in NP is solved by the non-deterministic Turing machine M, (M =

(Q, L F, 6) where Q =set of states, L =set of tape symbols, se Q initial st~tement F ~Q set of
accepting states and o = set of transition) and that M accepts or rejects an instance of the
iroblem in time p(n) where n is the size of the instance and p is a polynomial function.

We describe for each instance 'l' a Boolean exp~ession which is satisfiable if and only if the
machine M accepts l.

The Boolean expression uses the v~able set out in the following table, where qe Q, - p(n)~ i ~
p(n), jet and o ~ k ~ p(n):

Variables Intended Interpretation How many?

Tilt True if tape cell i contains symbol j at step k of the computation O(p(n)2)
Hill True if M's read/write head is at tape cell I at step k of the computation. O(p(n)2)
a~ True if Mis in state q at step k of computation O(p(n))

Derme the Boolean expression B to be the conjunction of the clauses in the following table, for
all- p(n)5 i ~ p(n) and ~ k~ p(n):
 8 / ( ),s
•14 UIIION Design and Analysis of Algorithm
How
man y?
Interpretations
Clauses Conditions O(p (n))
Tap e cell i of the input I Initial contents of th e tape 0(1 )
Tilo contains symbol i d
Initial state of M 0(1 )
·t hea
011c:1 Initial position of read/wn e O(p (n)')
Hnl'\ One symbol per tape cell
O(p (n)2)
Tnk. ➔ ., T1ik j *r Tape remains unch ange
d unle ss writt en
Ttjk = Tijk(k+ 1) O(p /n))
VHik Only one state at a time . O (p(n))
Q,,1, ➔ -,QQ'k q;t;q ' Only one head position at a t,m~ 2
O (p(n)
Possible transitions at. ~omputat,ons step
)
Hik ➔ -iH1 'k
i ;e i'
The disjunction of (q, cr, q', cr',d )e 5 k when hea d is at oos1t1on '
the clauses 0 (1)
st
The disjunction of Must finish in an acce pting ate
the clauses feF
0,1n tnll
by ass1 gnm g T ijk, H ik,
• . · ~ M on inpu t J, then B is sati sfia ble,
If ther e 1s an acce ptm g com puta tion 1or
_
and Qik thei r inte nde d interpretations.
t l that
e is an acce ptin g com puta tion for M on inpu
On the othe r band, if B is satisfiable, then ther
to the vari able s.
follo ws the steps indicated by the assi gnm ents
d in space
n vari able s, each of whi ch may be enc ode
How larg e is B? The re are O(p(n)2)Boolea
O(]og p(n)). .
nom ial in
size of B is O (Clo g p(n) p(n) 2). Thi s is poly
The num ber of clauses is O(p(n)2). · So the
is cert ainl y a poly nom ial·tim e redu ctio n.
n, the size of the input, so the tran sfor mat ion

:. Satisfiability prob lem is NP- Com plet e.

Consequences
inst anc e of
can be redu ced in poly nom ial tim e to an
The pro of show s that any prob lem in NP
cou ld be
ns that if the Boo lean sati sfia bili ty pro blem
Boo lean satisfiability prob lem . Thi s mea be
nom ial time by a dete rmin istic Tur ing mac hine , then all pro blem s in NP cou ld
solv ed in poly
ity clas s NP, wou ld be equ al to P.
solv ed in poly nom ial time, and so the com plex
John son
com plet ene ss 'for any pro blem . Gar ey and
Coo k's theo rem was the first pro of of NP
bili ty: A
lem s in thei r boo k com pute rs and Intr acta
pres ent mor e than 300 NP- Com plet e prob
The ory of NP- Com plet ene ss and . new pro blem s are still bein g add ed to the
guid e to the
com plex ity clas s.
 E~ornp\es
~~
~ ls the formula (~
p) " (p v q) " (
; ~\· ... q) satisfiable
.J ustify.
111tiOII
~ . n f0 nuula •
g1 1s
\le
i\'e
,- (P v q) " ( - q)
rP) p
0
0

. assigning truth va
lues to the form
S) th £.iven formula ula variables, the
is not satisfiable final formula does
$:), e . . . not have truth val
ue.
,._ If S is a set
of n elements, th
11 e powerset of S is
recursive algorith set of all possible
m to compute po subset of S. Write
werset of S.
solution
z\}gorithm for form
ing Pj(S)
Require: j ~ 0~ an ar
ray S such that le
ngth(S) :Sj~ a tem
Ensure: User defined porary array E of
code will be exec size j.
uted for each elem
o w e rs e tj (S ,j
) ent of E 2 Pj(S).
~ ro c e d u re p o // S ta r t th e a lg
w e rs e tj o ri th m
if > O th (U , s)
5 e n / / Recur dee
l le n g th (U) p e r' ?
for i + - 1 ,
l - s + 1
do
E ls ) + - U
(i )
p o w e rs e tj (U (l
+ i : 1), 5 // R e c u rs io n
end fo r - l)

e ~ :: r d e fi n e
d h a n d li n g
o f E re p re s e
end if n ti n g E 2 P j(
S ).
end p ro c e d u re
 Design and Analysis of Algorithm

Exercise
1. What is satisfiability problem? State cook' s theorem.

2. Is the fonnula (-p) A(p v q)" (- q) satisfiable. Justify.

3. Define Np-Hard and Np-Complete class of problems?

4. Define P and NP class. State Cook's theorem and eXplain its significance.

5. Write non-deterministic algorithm for max • clique decision problem.

6. Write a non-deterministic algorithm to solve knapsack problem.

7. Give a non-deterministic algorithm to solve 0/1 knapsack problem. What is its time

complexity?
8. If S is a set of n elements, the powerset of S is set of all possible subset of S. Write
recursive algorithm to compute powerset of S.
9. Write non-deterministic algorithm to sort set of n positive integers.

Questions Asked in Previous Exams

[Apr. 20171
1. Define P and NP class problems.

H!VM! [Oct. 201n

1. Write a non-deterministic algorithm for Max Clique decision problem.
[Oct. 20161
2. Write a non-deterministic algorithm to solve knapsack problem.

{,.I@
VISION