Kozen D.C. Theory of Computation
Подождите немного. Документ загружается.
394 References
[46] M. Furst, J. Saxe, and M. Sipser, Parity, circuits, and the poly-
nomial time hierarchy, Math. Syst. Theory, 17 (1984), pp. 13–27.
[47] K. G
¨
odel, On undecidable propositions of formal mathematical
systems, in The Undecidable,M.Davis,ed.,Hewlitt,NY:Raven
Press, 1965, pp. 5–38.
[48] O. Goldreich, S. Micali, and A. Wigderson, Proofs that yield
nothing but their validity, and a methodology of cryptographic pro-
tocol design, in Proc. 27th Symp. Foundations of Computer Science,
IEEE, October 1986, pp. 174–187.
[49] S. Goldwasser, S. Micali, and C. Rackoff, The knowledge
complexity of interactive proof systems, SIAM J. Comput.,18
(1989), pp. 186–208.
[50] S. Goldwasser and M. Sipser, Private coins vs. public coins in
interactive proof systems, in Proc. 18th Symp. Theory of Computing,
ACM, May 1986, pp. 59–68.
[51] G.H. Hardy and E.M. Wright, An Introduction to the Theory of
Numbers, 5th ed., Oxford, UK: Oxford University, 1979.
[52] D. Harel, Effective transformations on infinite trees, with appli-
cations to high undecidability, dominoes, and fairness, J. Assoc.
Comput. Mach., 33 (1986), pp. 224–248.
[53] D. Harel and D. Kozen, A programming language for the induc-
tive sets, and applications, Inf. Control, 63 (1984), pp. 118–139.
[54] D. Harel, D. Kozen, and J. Tiuryn, Dynamic Logic, Cambridge,
MA: MIT Press, 2000.
[55] J. Hartmanis and R.E. Stearns, On the computational complex-
ity of algorithms, Trans. Amer. Math. Soc., 117 (1965), pp. 285–306.
[56] J. H
˚
astad, Almost optimal lower bounds for small depth circuits,
in Proc. 18th Symp. Theory of Computing, New York: ACM, 1986,
pp. 6–20.
[57]
, Clique is hard to approximate within n
1−ε
, Acta Math., 182
(1999), pp. 105–142.
[58]
, Some optimal inapproximability results, J. Assoc. Comput.
Mach., 48 (2001), pp. 798–859.
[59] F.C. Hennie, One-tape off-line Turing machine computations, Inf.
Control, 8 (1965), pp. 553–578.
[60] F.C. Hennie and R.E. Stearns, Two-tape simulation of multitape
turing machines, J. Assoc. Comput. Mach., 13 (1966), pp. 533–546.
[61] J. Hopcroft, R. Motwani, and J. Ullman, Introduction to Au-
tomata Theory, Languages, and Computation, 2nd ed., Reading,
MA: Addison-Wesley, 2001.
[62] J.E. Hopcroft and R.M. Karp,Ann
5/2
algorithm for maximum
matching in bipartite graphs, SIAM J. Comput., 2 (1973), pp. 225–
231.
References 395
[63] J.E. Hopcroft and J.D. Ullman, Introduction to Automata The-
ory, Languages and Computation, Reading, MA: Addison-Wesley,
1979.
[64] D. Ierardi and D. Kozen, Parallel resultant computation, in Syn-
thesis of Parallel Algorithms, J. Reif, ed., San Francisco: Morgan
Kaufmann, 1993, pp. 679–720.
[65] N. Immerman, Nondeterministic space is closed under complement,
SIAM J. Comput., 17 (1988), pp. 935–938.
[66] D. Johnson, Approximation algorithms for combinatorial prob-
lems, J. Comput. Syst. Sci., 9 (1974), pp. 256–278.
[67] N.D. Jones, Space-bounded reducibility among combinatorial
problems, J. Comput. Syst. Sci., 11 (1975), pp. 68–85.
[68] N.D. Jones, E. Lien, and W. Laaser, New problems complete for
nondeterministic logspace, Math. Syst. Theory, 10 (1976), pp. 1–17.
[69] H. Karloff and U. Zwick, A 7/8 approximation algorithm for
MAX3SAT?, in Proc. 38th Symp. Foundations of Computer Science,
Los Alamitos, CA: IEEE, 1997, pp. 406–415.
[70] R.M. Karp, Reducibility among combinatorial problems, in Com-
plexity of Computer Computations, R.E. Miller and J.W. Thatcher,
eds., New York: Plenum, 1972, pp. 85–103.
[71] S.C. Kleene, A theory of positive integers in formal logic, Amer.
J. Math., 57 (1935), pp. 153–173, 219–244.
[72]
, On notation for ordinal numbers, J. Symbolic Logic,42
(1938), pp. 150–155.
[73]
, Introduction to Metamathematics, Princeton, NJ: D. van Nos-
trand, 1952.
[74]
, On the forms of the predicates in the theory of constructive
ordinals (second paper), Amer.J.Math., 77 (1955), pp. 405–428.
[75] D. Kozen, The Design and Analysis of Algorithms,NewYork:
Springer-Verlag, 1991.
[76]
, Automata and Computability, New York: Springer-Verlag,
1997.
[77]
, Computational inductive definability, Ann. Pure Appl. Logic,
126 (2004), pp. 139–148.
[78] R.A. Ladner, The circuit value problem is logspace complete for
P, SIGACT News, 7 (1975), pp. 18–20.
[79] L.A. Levin, Universal sorting problems, Prob. Inf. Transmission,9
(1973), pp. 265–266.
[80] L. Lov
´
asz, On determinants, matchings, and random algorithms,
in Proc. Symp. on Fundamentals of Computing Theory, L. Budach,
ed., Berlin: Akademia-Verlag, 1979, pp. 565–574.
396 References
[81] C. Lund, L. Fortnow, H. Karloff, and N. Nisan, Algebraic
methods for interactive proof systems, J. Assoc. Comput. Mach.,39
(1992), pp. 859–868.
[82] S.R. Mahaney, Sparse complete sets for NP: solution of a conjec-
ture by Berman and Hartmanis, J. Comput. Syst. Sci., 25 (1982),
pp. 130–143.
[83] E.M. McCreight and A.R. Meyer, Classes of computable func-
tions defined by bounds on computation: Preliminary report, in
Proc. 1st ACM Symp. Theory of Computing (STOC’69),NewYork:
ACM, 1969, pp. 79–88.
[84] R. McNaughton, Testing and generating infinite sequences by a
finite automaton, Inf. Control, 9 (1966), pp. 521–530.
[85] A.R. Meyer and D.M. Ritchie, The complexity of loop programs,
in Proc. ACM Natl. Meeting, 1967, pp. 465–469.
[86] G.L. Miller, Riemann’s hypothesis and tests for primality, J. Com-
put. Syst. Sci., 13 (1976), pp. 300–317.
[87] Y.N. Moschovakis, Elementary Induction on Abstract Structures,
Amsterdam: North-Holland, 1974.
[88] A.A. Muchnik, On the unsolvability of the problem of reducibil-
ity in the theory of algorithms, Doklady Akademii Nauk SSSR, 108
(1956), pp. 194–197.
[89] D. Muller, Infinite sequences and finite machines, in Proc. 4th
Symp. Switching Circuit Theory and Logical Design, Los Alamitos,
CA: IEEE, 1963, pp. 3–16.
[90] J. Myhill, Creative sets, Zeitschrift f¨ur mathematische Logik und
Grundlagen der Mathematik, 1 (1955), pp. 97–108.
[91] D.C. Oppen, An upper bound on the complexity of Presburger
arithmetic, J. Comput. Syst. Sci., 16 (1978), pp. 323–332.
[92] C.H. Papadimitriou, NP-completeness: A retrospective, in 24th
Int. Colloq. Automata, Languages and Programming (ICALP’97),
P. Degano, R. Gorrieri, and A. Marchetti-Spaccamela, eds., vol. 1256
of Lecture Notes in Computer Science, Bologna, Italy, New York:
Springer-Verlag, July 1997, pp. 2–6.
[93] C.H. Papadimitriou and S. Zachos, Two remarks on the power
of counting, in Proc. 6th GI Conf. Theoretical Computer Science,
New York: Springer-Verlag, 1982, pp. 269–276.
[94] E.L. Post, Finite combinatory processes-formulation, I, J. Symbolic
Logic, 1 (1936), pp. 103–105.
[95]
, Formal reductions of the general combinatorial decision prob-
lem, Amer.J.Math., 65 (1943), pp. 197–215.
[96]
, Recursively enumerable sets of positive integers and their
decision problems, Bull. Amer. Math. Soc., 50 (1944), pp. 284–316.
References 397
[97] V.R. Pratt, Every prime has a succinct certificate, SIAM J. Com-
put., 4 (1975), pp. 214–220.
[98] M. Presburger,
¨
Uber die Vollst¨andigkeit eines gewissen Systems
der Arithmetik ganzer Zahlen, in welchen die Addition als einzige
Operation hervortritt, Comptes Rendus, I. Congr`es des Math. des
Pays Slaves, (1929), pp. 192–201.
[99] M.O. Rabin, Decidability of second order theories and automata
on infinite trees, Trans. Amer. Math. Soc., 141 (1969), pp. 1–35.
[100]
, Probabilistic algorithms for testing primality, J. Num. The-
ory, 12 (1980), pp. 128–138.
[101] O. Reingold, Undirected ST-connectivity in log-space, in Proc.
37th Symp. Theory of Computing, New York: ACM, May 2005,
pp. 376–385.
[102] H.G. Rice, Classes of recursively enumerable sets and their decision
problems, Trans. Amer. Math. Soc., 89 (1953), pp. 25–59.
[103]
, On completely recursively enumerable classes and their key
arrays, J. Symbolic Logic, 21 (1956), pp. 304–341.
[104] H. Rogers, Theory of Recursive Functions and Effective Com-
putability, New York: McGraw-Hill, 1967.
[105] R. Rubinfeld and M. Sudan, Robust characterizations of poly-
nomials with applications to program testing, SIAM J. Comput.,25
(1996), pp. 252–271.
[106] W. Ruzzo, On uniform circuit complexity, J. Comput. Syst. Sci.,
22 (1981), pp. 365–383.
[107] S. Safra,Onthecomplexityofω-automata, in Proc. 29th Symp.
Foundations of Comput. Sci, Los Alamitos, CA: IEEE, October
1988, pp. 319–327.
[108] W. Savitch, Relationship between nondeterministic and determin-
istic tape complexities, J. Comput. Syst. Sci., 4 (1970), pp. 177–192.
[109] M. Sch
¨
onfinkel,
¨
Uber die Bausteine der mathematischen Logik,
Math. Annalen, 92 (1924), pp. 305–316.
[110] J.T. Schwartz, Fast probabilistic algorithms for verification of
polynomial identities, J. Assoc. Comput. Mach., 27 (1980), pp. 701–
717.
[111] A. Shamir, IP = PSPACE ,inProc. 31st Symp. Foundations of
Computer Science, Los Alamitos, CA: IEEE, 1990, pp. 11–15.
[112] M. Sipser, A complexity theoretic approach to randomness, in Proc.
15th Symp. Theory of Computing, New York: ACM, 1983, pp. 330–
335.
[113]
, Introduction to the Theory of Computation,PacificGrove,
CA: Brooks Cole, 1996.
398 References
[114] R.I. Soare, Recursively Enumerable Sets and Degrees, Berlin:
Springer-Verlag, 1987.
[115] R. Stearns, J. Hartmanis, and R. Lewis, Hierarchies of mem-
ory limited computations, in Proc. IEEE Conf. Switching Circuit
Theory and Logical Design, 1965, pp. 179–190.
[116] L. Stockmeyer and A. Chandra, Provably difficult combinato-
rial games, SIAM J. Comput., 8 (1979), pp. 151–174.
[117] L.J. Stockmeyer, The polynomial-time hierarchy, Theor. Comput.
Sci., 3 (1976), pp. 1–22.
[118] L.J. Stockmeyer and A.R. Meyer, Word problems requiring ex-
ponential time, in Proc. 5th Symp. Theory of Computing,NewYork:
ACM, 1973, pp. 1–9.
[119] R. Szelepcs
´
enyi, The method of forcing for nondeterministic au-
tomata, Bull. EATCS, 33 (1987), pp. 96–100.
[120] S. Toda, On the computational power of PP and ⊕P,inProc. 30th
Symp. Foundations of Computer Science (FOCS’89), Los Alamitos,
CA: IEEE, 1989, pp. 514–519.
[121]
, PP is as hard as the polynomial-time hierarchy, SIAM J.
Comput., 20 (1991), pp. 865–877.
[122] B.A. Trakhtenbrot, Turing computations with logarithmic delay,
Algebra i Logika, 3 (1964), pp. 33–48.
[123] A.M. Turing, On computable numbers with an application to
the Entscheidungsproblem, Proc. London Math. Soc., 42 (1936),
pp. 230–265. Erratum: Ibid., 43 (1937), pp. 544–546.
[124] L.G. Valiant, The complexity of computing the permanent, Theor.
Comput. Sci., 8 (1979), pp. 189–201.
[125] L.G. Valiant and V.V. Vazirani, NP is as easy as detecting
unique solutions, in Proc. 17th ACM Symp. Theory of Computing
(STOC’85), New York: ACM, 1985, pp. 458–463.
[126] A.C. Yao, Separating the polynomial-time hierarchy by oracles, in
Proc. 26th Symp. Foundations of Computer Science (FOCS’85),Los
Alamitos, CA: IEEE, 1985, pp. 1–10.
[127] R.E. Zippel, Probabilistic algorithms for sparse polynomials, in
Proc. EUROSAM 79, Ng, ed., vol. 72 of Lect. Notes in Comput.
Sci., New York: Springer-Verlag, 1979, pp. 216–226.
Notation and Abbreviations
TM Turing machine......................................4
Σ finite alphabet.......................................5
|x| length of string x ....................................5
|A| cardinality of set A ..................................5
ε null string...........................................5
Σ
∗
finite-length strings over Σ...........................5
left endmarker.......................................5
Γ tape alphabet........................................5
blank symbol........................................5
L(M) set of strings accepted by Turing machine M .........5
δ transition relation of a Turing machine. . . . . . . . . . . . . . .6
PAL palindromes.........................................7
b
k
(i) k-bit binary representation of i ......................8
T (n) time bound.........................................11
N natural numbers....................................11
S(n) space bound........................................11
400 Notation and Abbreviations
n length of input string . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
DTIME(T (n)) deterministic time class.............................12
NTIME(T (n)) nondeterministic time class.........................12
DSPACE(S(n)) deterministic space class............................12
NSPACE(S(n)) nondeterministic space class........................12
co-A set of complements of sets in A .....................12
LOGSPACE deterministic logspace..............................12
NLOGSPACE nondeterministic logspace...........................12
P deterministic polynomial time ......................13
NP nondeterministic polynomial time...................13
PSPACE deterministic polynomial space......................13
NPSPACE nondeterministic polynomial space..................13
EXPTIME deterministic exponential time......................13
NEXPTIME nondeterministic exponential time ..................13
EXPSPACE deterministic exponential space.....................13
NEXPSPACE nondeterministic exponential space .................13
≤k
−→ configuration accessibility relation . . . . . . . . . . . . . . . . . . 15
#(x) number represented by binary numeral x............17
k-FA k-headed finite automaton..........................26
≤
log
m
logspace many–one reducibility . . . . . . . . . . . . . . . . . . . . . 27
≤
p
m
polynomial-time many–one reducibility . . . . . . . . . . . . . 27
MAZE directed graph reachability. . . . . . . . . . . . . . . . . . . . . . . . . .28
SAT Boolean satisfiability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30
CVP circuit value problem...............................30
CNF conjunctive normal form............................34
k-CNF k-conjunctive normal form..........................34
3SAT satisfiability problem for 3CNF formulas . . . . . . . . . . . . 34
Notation and Abbreviations 401
ω smallest infinite ordinal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
α,β,γ,... ordinals............................................36
Ord class of all ordinals.................................36
ZF Zermelo–Fraenkel set theory........................38
sup A supremum of set A .................................38
x ∨ y join of x and y in a lattice..........................38
maximum element of a complete lattice.............38
⊥ minimum element of a complete lattice .............38
inf A infimum of set A....................................38
C union of a class of sets C ............................38
C intersection of a class of sets C ......................38
PF
τ
(x) prefixpoints of τ above x ........................... 40
τ
†
(x) least prefixpoint of τ above x .......................40
ι identity relation....................................41
ATM alternating Turing machine.........................45
information order...................................46
λx.E(x) functional abstraction ..............................46
ATIME (T (n)) alternating time class...............................48
ASPACE(S(n)) alternating space class..............................48
ALOGSPACE alternating logspace................................48
APTIME alternating polynomial time ........................48
APSPACE alternating polynomial space........................48
AEXPTIME alternating exponential time........................48
QBF quantified Boolean formula problem ................ 51
PH polynomial-time hierarchy..........................57
Σ
p
k
class in the polynomial-time hierarchy..............58
Π
p
k
class in the polynomial-time hierarchy..............58
402 Notation and Abbreviations
∼A complement of set A ................................58
H
k
generic complete problem for Σ
p
k
....................58
P
B
relativized complexity class.........................60
NP
B
relativized complexity class.........................60
P
C
relativized complexity class.........................60
NP
C
relativized complexity class.........................60
P
NP
relativized complexity class.........................60
NP
NP
relativized complexity class.........................60
∃
t
, ∀
t
bounded quantifiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64
PRAM parallel random access machine . . . . . . . . . . . . . . . . . . . . . 66
NC parallel complexity class............................66
STA(S(n),T(n),A(n)) complexity class: space, time, alternations . . . . 69
BPP bounded probabilistic polynomial time . . . . . . . . . . . . . . 74
RP random polynomial time............................74
Pr(E) probability of event E ..............................75
EX expected value of random variable X ...............75
Pr(E | F ) conditional probability of E given F ................75
E(X | E) conditional expectation of X given E ...............75
Pr
y
(E) probability of event E with random bits y ..........78
F field................................................79
det X determinant of matrix X ...........................80
Z
p
field of integers modulo prime p.....................80
⊕ exclusive or.........................................84
Z
n
ring of integers modulo n ...........................86
x mod n remainder of x modulo n ...........................86
x ≡ y (mod n) x congruent to y modulo n .........................87
PRIMES set of binary representations of primes..............90
Notation and Abbreviations 403
R
∗
invertible elements of a ring R ......................91
ϕ(n) Euler ϕ function....................................91
GF
q
field with q elements................................92
m | nmdivides n ........................................92
F algebraic closure of field F ..........................95
IP efficient interactive proofs...........................99
P prover..............................................99
V verifier.............................................99
Z ring of integers....................................105
PCP probabilistically checkable proofs . . . . . . . . . . . . . . . . . . 113
PCP(r(n),q(n)) PCP with O(r(n)) random bits and O(q(n)) queries . . 114
PTAS polynomial-time approximation scheme............114
DNF disjunctive normal form ........................... 117
x
•
y inner product......................................120
⊗ tensor product.....................................124
u
T
transpose of u .....................................126
rank C rank of matrix C ..................................127
dim E dimension of linear space E ........................127
f
A
interpretation of symbol f in structure A ..........129
0 falsity.............................................129
1 truth..............................................130
u[x/a] rebinding of variable x to value a in valuation u . . . 130
satisfaction........................................132
Th(A) first-order theory of structure A ...................133
Th(C) first-order theory of class of structures C ...........133
Mod(Φ) models of Φ.......................................134
Q rational numbers..................................136