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

The first examines simulation of one computational model by another for a large range of
models. The second provides a large catalog of complexity classes and relationships between
them. The third examines parallel algorithms and complexity. Other sources for more infor-
mation on this topic are the topics by Hopcroft and Ullman [ 141 ], Lewis and Papadimitriou
[ 200 ], Balcazar, Dıaz, and Gabarro on structural complexity [ 27 ], Garey and Johnson [ 109 ]
on the theory of NP -completeness, Greenlaw, Hoover, and Ruzzo [ 120 ]on P -completeness,
and Papadimitriou [ 235 ] on computational complexity.
The Turing machine was defined by Alan Turing in 1936 [ 338 ], as was the oracle Turing
machine. Random-access machines were introduced by Shepherdson and Sturgis [ 308 ]and
the performance of RAMs was analyzed by Cook and Reckhow [ 77 ].
Hartmanis, Lewis, and Stearns [ 127 , 128 ] gave the study of time and space complexity
classes its impetus. Their papers contain many of the basic theorems on complexity classes,
including the space and time hierarchy theorems stated in Section 8.5.1 . The gap theorem
was obtained by Trakhtenbrot [ 334 ] and rediscovered by Borodin [ 51 ]. Blum [46] developed
machine-independent complexity measures and established a speedup theorem showing that
for some languages there is no single fastest recognition algorithm [ 47 ].
Many individuals identified and recognized the importance of the classes P and NP . Cook
[ 74 ]formalized NP , emphasized the importance of polynomial-time reducibility, and exhib-
ited the first NP -complete problem, SATISFIABILITY . Karp [ 159 ] then demonstrated that
a number of other combinatorial problems, including TRAVELING SALESPERSON ,are NP -
complete. Cook used Turing reductions in his classification whereas Karp used polynomial-
time transformations. Independently and almost simultaneously Levin [ 199 ] (see also [335])
was led to concepts similar to the above.
The relationship between nondeterministic and deterministic space (Theorem 8.5.5 and
Corollary 8.5.1 ) was established by Savitch [ 297 ]. The proof that nondeterministic space
classes are closed under complementation (Theorem 8.6.2 and Corollary 8.6.2 ) is indepen-
dently due to Szelepscenyi [ 322 ] and Immerman [ 145 ].
Theorem 8.6.4 ,showingthat PRIMALITY is in NP

∩

coNP ,isduetoPratt[ 257 ].
Cook [ 75 ] defined the concept of a P -complete problem and exhibited the first such prob-
lem. He was followed quickly by Jones and Laaser [ 153 ] and Galil [108]. Ladner [185] showed
that circuits simulating Turing machines (see [ 286 ]) could be constructed in logarithmic space,
thereby establishing that CIRCUIT VALUE is P -complete. Goldschlager [ 117 ]demonstrated
that MONOTONE CIRCUIT VALUE is P -complete. Valiant [ 345 ] and Cook established that
LINEAR INEQUALITIES is P -hard, and Khachian [ 165 ] showed that this problem is in P .The
proof that DTM ACCEPTANCE is P -complete is due to Johnson [ 151 ].
Cook [ 74 ] gave the first proof that SATISFIABILITY is NP -complete and also gave the
reduction to 3- SAT . Independently, Levin [ 199 ](seealso[ 335 ]) was led to similar concepts
for combinatorial problems. Schafer [ 299 ] showed that NAESAT is NP -complete. Karp [ 159 ]
established that 0-1 INTEGER PROGRAMMING ,3- COLORING , EXACT COVER , SUBSET
SUM , TASK SEQUENCING ,and INDEPENDENT SET are NP -complete.
The proof that 2- SAT is in NL (Theorem 8.11.1 ) is found in Papadimitriou [ 235 ].
Karp [ 159 ] exhibited a PSPACE -complete problem, Meyer and Stockmeyer [ 316 ]demon-
strated that QUANTIFIED SATISFIABILITY is PSPACE -complete and Schafer established that
GENERALIZED GEOGRAPHY is PSPACE -complete [ 299 ].
The notion of a uniform circuit was introduced by Borodin [ 52 ] and has been examined by
many others. (See [120].) Borodin [ 52 ] established the connection between nondeterministic