Machines with Memory - Models of Computation: Exploring the Power of Computing - page 128

COROLLARY 3.9.1 Let the function f be computed by an m -word, b -bit one-tape Turing machine
in T steps, b fixed. Then, over any complete basis Ω the following inequality must hold:
C Ω ( f )= O T 2

Thereisnolossinassumingthatalanguage L is a set of strings over a binary alpha-
bet; that is, L

⊆B ∗ . As explained in Section 1.2.3 , a language can be defined by a family

n

{ f 1 , f 2 , f 3 , ... }

of characteristic (Boolean) functions, f n :

B →B

,whereastring w of

length n is in L if and only if f n ( w )= 1.
Theorem 3.9.2 not only establishes a clear connection between Turing time complexity
and circuit size complexity, but it also provides a potential means to resolve the question P =
NP of whether P and NP are equal or not. Circuit complexity is currently believed to be the
most promising tool to examine this question. (See Chapter 9 .)

3.9.3 Reductions from Turing to Circuit Computations
As shown in Theorem 3.9.1 ,acircuit C M , T can be constructed that simulates a time- and

space-bounded computation by either a deterministic or a nondeterministic Turing machine
M .If M is deterministic and accepts the binary input string w ,then C M , T has value 1 when

supplied with the value of w .If M is nondeterministic and accepts the binary input string w ,
then for some values of the binary choice variables c ,

C M , T on inputs w and c has value 1.
The language of strings describing circuits with fixed inputs whose value on these inputs
is 1 is called CIRCUIT VALUE . When the circuits also have variable inputs whose values can
be chosen so that the circuits have value 1, the language of strings describing such circuits is
called CIRCUIT SAT .(SeeSection 3.9.6 .) The languages CIRCUIT VALUE and CIRCUIT SAT
are examples of P -complete and NP -complete languages, respectively.
The P -complete and NP -complete languages play an important role in complexity the-
ory: they are prototypical hard languages. The P -complete languages can all be recognized in
polynomial time on serial machines, but it is not known how to recognize them on parallel
machines in time that is a polynomial in the logarithm of the length of strings (this is called
poly-logarithmic time ), which should be possible if they are parallelizable. The NP -complete
languages can be recognized in exponential time on deterministic serial machines, but it is
not known how to recognize them in polynomial time on such machines. Many important
problems have been shown to be P -complete or NP -complete.
Because so much effort has been expended without success in trying to show that the
NP -complete ( P -complete) languages can be solved serially (in parallel) in polynomial (poly-
logarithmic) time, it is generally believed they cannot. Thus, showing that a problem is NP -
complete ( P -complete) is considered good evidence that a problem is hard to solve serially (in
parallel).
To obtain such results, we exhibit a program that writes the description of the circuit C M , T

from a description of the TM M and the values written initially on its tape. The time and
space needed by this program are used to classify languages and, in particular, to identify the
P -complete and NP -complete languages.
The simple program

shown schematically in Fig. 3.27 writes a description of the circuit
C M , T of Fig. 3.25 , which is deterministic or nondeterministic depending on the nature of
M . (Textual descriptions of circuits are given in Section 2.2 . Also see Problem 3.8 .) The
first loop of this program reads the value of i th input letter w i of the string w written on

P