Suppose that no efficient algorithm is known for the decision problem Q, but that Q e NP. Show that an exponential-time deterministic algorithm exists for Q. (Let the NDTM which verifies Q in time...

1. 
   

   
   Suppose that no efficient algorithm is known for the decision problem
   
   Q,
   
   but that
   
   Q
   
   e
   
   NP.
   
   Show that an exponential-time deterministic algorithm exists for
   
   Q.
   
   

   
   

(Let the

NDTM

which verifies

Q

in time

p(n)

be changed into a

DTM



which checks all possible guesses in series. The time required for this

DTM

is of order p(n)ITl

^111ttl

where

T is

the set of tape symbols.)