The Theory of Computation

Bernard M.E. Moret

Addison-Wesley-Longman, 1998


Detailed Solutions

Chapter 6, Problem 6




What we need to prove is that, if some problem A is in P and some problem B many-one reduces to A in polynomial time, then B is also in P; the we should repeat for EXP; finally we need to show that such need not be the case for E.

We begin with P. Since A is in P, there is a Turing machine M and a polynomial p such that M can decide an instance x of A in time p(|x|). Let f be the polynomial-time transformation from B to A and let q be its polynomial bound. We build a decision machine M' for B by using the machine M for A and the the transformation f. Specifically, M' will decide an instance x of B by transforming it in time q(|x|) to an instance y=f(x) of A and running the decision procedure M on y in p(|y|) time. Since the transformation takes time q(|x|), what it produces, the string y, cannot exceed q(|x|) in length; thus the time taken by solver M, which is p(|y|), is at most p(q(|x|)), which is a polynomial in |x|. Hence our solver M' runs in time polynomial in |x| and thus B is in P.

The same reasoning applies if we replace the polynomial bound p by an exponential bound of the type 2nk for some positive integer k, since we can bound any quantity of the form 2qk(n) by another exponential of the form 2nm for a suitable choice of m.

However, if the bound is a bound for E, that is a bound of the form 2kn, then the running time after the transformation is of the form 2kq(n), which, if q is a polynomial of degree higher than 1, cannot be bounded by any function of the form 2mn for any constant m. Thus E need not be closed under polynomial-time transformations. To prove that it is actually not closed, we need a specific counterexample; that is much harder, since it requires knowledge of specific problems with specific lower bounds -- we would need to know of at least one problem requiring more time than is available in E and that happens to reduce to some problem in E in polynomial time.