Chapter 12: Complexity f;;! 351
We have seen that a deterministic TM i'vJ I simulating a nondetenninistic
TM At exists (refer to Theorem 9.3). If T(n) is the complexity of M, then the
complexity of the equivalent deterministic TM M I is 2°!TIII)). This can be
justified as follows. The processing of an input string w of length n by M is
equivalent to a ·tree' of computations by M j • Let k be the maximum of the
number of choices forced by the nondeterministic transition function. (It is
maxlo(q, .1.')1, the maximum taken over all states q and all tape symbol K)
Every branch of the computation tree has a length T(n) or less. Hence the total
number of leaves is atmost kT(n). Hence the complexity of M I is at most
20ITII/I)
It is not known whether the complexity of M] is less than 2°([(11)). Once
again an answer to this question will prove or disprove P 1= NP. But there do
exist algorithms where T(n) lies between a polynomial and an exponential
function (refer to Section 12.1).
12.3 POLYNOMIAL TIME REDUCTION AND
NP-COMPLETENESS
If P j and P~ are t\vo problems and P~ EO P, then we can decide whether
Pi EO P by relating the t\VO problems P j and P~. If there is an algorithm for
obtaining an instance of P~ given any instance of Pj, then we can decide about
the problem P j' Intuitively if this algOlithm is a polynomial one, then the
problem PI can be decided in polynomial time.
DefInition 12.8 Let PI and P~ be two problems. A reduction from PI to P~
is an algorithm which converts an instance of PI to an instance of P~. If the
time taken by the algOlithm is a polynomial pen), n being the length of the
input of Pj. then the reduction is called a polynomial reduction PI to P~.
Theorem 12.3 If there is a polynomial time reduction from P j to P: and if
P: is in P then P j is in P.
Proof Let In denote the size of the input of PI' As there is a polynomialtime reduction of P j to P:. the corresponding instance of P~ can be got in
polynomial-time. Let it be O(;1'zi), So the size of the resulting input of P: is
atmost Cln! for some constant c. As P~ is in P. the time taken for deciding the
membership in P: is O(ni:} n being the size of the input of P:. So the total
time taken for deciding the membership of m-size input of P I is the sum of
the time taken for conversion into an instance of p, and the time for decision
of the corresponding input in P~. This is O[m i + (cmjll which is the same
as o(m fk ). So PI is in P.
Definition 12.9 Let L be a language or problem in NP. Then L is NPcomplete if
1. L is in NP
We have seen that a deterministic TM i'vJ I simulating a nondetenninistic
TM At exists (refer to Theorem 9.3). If T(n) is the complexity of M, then the
complexity of the equivalent deterministic TM M I is 2°!TIII)). This can be
justified as follows. The processing of an input string w of length n by M is
equivalent to a ·tree' of computations by M j • Let k be the maximum of the
number of choices forced by the nondeterministic transition function. (It is
maxlo(q, .1.')1, the maximum taken over all states q and all tape symbol K)
Every branch of the computation tree has a length T(n) or less. Hence the total
number of leaves is atmost kT(n). Hence the complexity of M I is at most
20ITII/I)
It is not known whether the complexity of M] is less than 2°([(11)). Once
again an answer to this question will prove or disprove P 1= NP. But there do
exist algorithms where T(n) lies between a polynomial and an exponential
function (refer to Section 12.1).
12.3 POLYNOMIAL TIME REDUCTION AND
NP-COMPLETENESS
If P j and P~ are t\vo problems and P~ EO P, then we can decide whether
Pi EO P by relating the t\VO problems P j and P~. If there is an algorithm for
obtaining an instance of P~ given any instance of Pj, then we can decide about
the problem P j' Intuitively if this algOlithm is a polynomial one, then the
problem PI can be decided in polynomial time.
DefInition 12.8 Let PI and P~ be two problems. A reduction from PI to P~
is an algorithm which converts an instance of PI to an instance of P~. If the
time taken by the algOlithm is a polynomial pen), n being the length of the
input of Pj. then the reduction is called a polynomial reduction PI to P~.
Theorem 12.3 If there is a polynomial time reduction from P j to P: and if
P: is in P then P j is in P.
Proof Let In denote the size of the input of PI' As there is a polynomialtime reduction of P j to P:. the corresponding instance of P~ can be got in
polynomial-time. Let it be O(;1'zi), So the size of the resulting input of P: is
atmost Cln! for some constant c. As P~ is in P. the time taken for deciding the
membership in P: is O(ni:} n being the size of the input of P:. So the total
time taken for deciding the membership of m-size input of P I is the sum of
the time taken for conversion into an instance of p, and the time for decision
of the corresponding input in P~. This is O[m i + (cmjll which is the same
as o(m fk ). So PI is in P.
Definition 12.9 Let L be a language or problem in NP. Then L is NPcomplete if
1. L is in NP