Complexity Classes - Models of Computation: Exploring the Power of Computing - page 355

Since the length of the input x is provided in unary, that is, by the number of characters
it contains, its length n canbewritteninbinaryonaworktapeinspace O (log n ) by
counting the number of characters in x . Since it is not difficult to show that any power of
a k -bit binary number can be computed by a DTM in work space O ( k ) , it follows that any
fixed polynomial in n can be computed by a DTM in work space O ( k )= O (log n ) .(See
Problem 8.18 .)
To s h ow t h a t DTM ACCEPTANCE is in P , we design a Turing machine that accepts the
“Yes” instances in polynomial time. This machine copies the unary string of length n to one
of its work tapes. Given the description of the DTM M , it simulates M with a universal
Turing machine on input w . When it completes a step, it advances the head on the work
tape containing n in unary, declaring the instance of DTM ACCEPTANCE accepted if M
terminates without using more than n steps. By definition, it will complete its simulation of
M in at most n of M 's steps each of which uses a constant number of steps on the simulating
machine. That is, it accepts a “Yes” instance of DTM ACCEPTANCE in time polynomial in
the length of the input.

8.10 NP -Complete Problems
As mentioned above, the NP -complete problems are the problems in NP that are the most
difficult to solve. We have shown that NP

⊆ ⊆

EXPTIME or that every problem in
NP , including the NP -complete problems, can be solved in exponential time. Since the NP -
complete problems are the hardest problems in NP , each of these is at worst an exponential-
time problem. Thus, we know that the NP -complete problems require either polynomial or
exponential time, but we don't know which.
The CIRCUIT SAT problem is to determine from a description of a circuit whether it can
be satisfied ; that is, whether values can be assigned to its inputs such that the circuit output
has value 1. As mentioned above, this is our canonical NP -complete problem.

PSPACE

CIRCUIT SAT
Instance: A circuit description with n input variables

{ x 1 , x 2 , ... , x n }

for some integer n

and a designated output gate.
Answer: “Yes” if there is an assignment of values to the variables such that the output of the
circuit has value 1.
As shown in Section 3.9.6 , CIRCUIT SAT is an NP -complete problem. The goal of this
problemistorecognizethe“Yes”instancesof CIRCUIT SAT , instances for which there are
values for the input variables such that the circuit has value 1.
In Section 3.9.6 we showed that CIRCUIT SAT described above is NP -complete by demon-
strating that for every decision problem P in NP an instance w of P and an NDTM M that

accepts “Yes” instances of can be translated by a polynomial-time (actually, a log-space)

DTM into an instance c of CIRCUIT SAT such that w is a “Yes” instance of

P

P if and only if c

is a “Yes” instance of CIRCUIT SAT .
Although it suffices to reduce problems in NP via a polynomial-time transformation to an
NP -complete problem, each of the reductions given in this chapter can be done by a log-space
transformation. We now show that a variety of other problems are NP -complete.