Kozen D.C. Theory of Computation
Подождите немного. Документ загружается.
Index 415
monadic second-order theory
of n successors, 154
of successor, 154–159
monoid homomorphism, 160
monotone, 39, 258, 261, 292, 313, 370
Monte Carlo algorithm, 95
Motwani, Rajeev, 116
µ-recursive function, 4, 287
Muchnik, A. A., 247, 253
Muller, David E., 157, 161
Muller acceptance, 157
Muller automaton, 155, 157–159, 161,
284, 347
Myhill, John R., 310
n-ary, 129
natural logarithm, 375
natural numbers, 35, 154
NC , 66, 79, 193
NC = P,67
negative condition, 254
next-configuration relation, 72
Nick’s class, 66
Nisan, Noam, 103
nonadaptive, 113
nonsingular, 300
normal extension, 96
NP, 186
null string, 5
nullary, 129
number theory, 284, 314, 316
first-order, 257
second-order, 257
Ogihara, Mitsunori, 299
ω-tree, 263, 270
recursive, 264
one-way function, 294
one-counter automaton, 280, 332
operator, 39
chain-continuous, 39
closure, 40
finitary, 39
monotone, 39
on complexity classes, 186
set, 39
Oppen, Derek C., 151
oracle, 59, 60, 63, 110, 113, 194
branch, 117
Turing machine, 57, 59, 194
order, 90, 95
ordered tree, 80
ordinal, 35–37
finite, 35
limit, 37
recursive, 263, 264
successor, 37
orthogonal complement, 181, 188
output polynomial time, 302
P = NP, 4, 15, 28, 115, 171, 175
padding, 228–229, 290, 364, 365
pairing, 221, 238, 257
palindrome, 7
parallel
complexity, 66–73
random access machines, 66
parity, 193, 209
partial
function, 173
order, 129, 136, 204
complete, 292
recursive function, 220
valuation, 198, 204, 304
random, 193, 196, 199, 305
path, 264, 270
PCP theorem, 114
Peano arithmetic, 314, 315, 387
perfect matching, 79
PH ,57
Π
1
1
, 257, 264
Π
k
-machine, 58
Pippenger, Nicholas, 66
Poisson trials, 211, 213
polynomial, 80
factorization, 80, 95–98
gcd, 67
space, 13
time, 13
zero testing, 78
polynomial-time
approximation scheme, 114
hierarchy, 57–65, 180, 185, 192,
236, 280
many–one reducibility, 27
416 Index
transducer, 28
Turing reducibility, 61
uniform, 280
positive condition, 254
positive occurrence, 261, 303
Post, Emil, 3, 247
Post correspondence problem, 160,
308, 364
Post system, 4
Post’s problem, 247, 253–256
Post’s theorem, 247, 248, 250–252,
255
postfix, 130
PP, 186
Pratt, Vaughan, 90
prefix order, 373
prefixpoint, 39, 292
prenex form, 54, 133, 138, 143, 375
Presburger, Mojzesz, 151
Presburger arithmetic, 151–153
primality test, 81, 90–94, 103
prime, 20, 81, 90
factorization, 91
relatively, 20, 86, 87, 91
subfield, 91, 95
primitive
recursion, 307, 382
recursive function, 287, 306–308
priority argument, 247, 253, 254, 385
probabilistic
complexity, 74–85
Turing machine, 74, 77
probabilistically checkable proof,
113–127, 296
probability
conditional, 75, 127
discrete, 74–77, 211–214
productive function, 249, 251
productive set, 249, 311
projection, 221, 261, 307
promise problem, 389
proper class, 36
prover, 99
PTAS, 114
pumping lemma, 343
pushdown automaton
alternating, 367
QBF, 51, 103, 172, 347, 362, 375
quantified Boolean formula, 51
quantifier, 131
alternation, 237
prefix, 65, 237
Quine, Willard van Orman, 227
quine, 227, 308, 309
quotient ring, 87, 96
Rabin
acceptance, 161, 269
automaton, 155, 161, 167
Rabin, Michael O., 81, 90, 140, 146,
147, 151, 154, 161
Rackoff, Charles, 102, 135, 140, 151
random
basis, 181
bits, 77, 99, 109, 114, 117, 188
branch, 117
input, 81
matrix, 363
NC , 79, 80
nonsingular matrix, 188, 301,
363
oracle hypothesis, 171
partial valuation, 196, 199, 305
permutation, 102
polynomial time, 74, 78, 183
self-correction, 121, 125
tower, 180, 188
variable, 75, 181, 199, 211, 305
randomness, 78
rank, 127
rational numbers, 136
r.e., 227
-complete, 239, 247
-hard, 239
in, 236
real
addition, 140
closed field, 140
numbers, 136
rebinding operator, 130
recursion theorem, 224–230, 234, 285,
286, 309, 352, 355, 358, 364,
365, 384
recursive
Index 417
function
partial, 220
total, 220
in, 236
isomorphism, 229, 230
ordinal, 258, 263, 264
recursively
enumerable, 227
separable, 311
reduced form, 143
reducibility
Cook, 61
Karp, 27
many–one, 239
logspace, 27
polynomial-time, 27
Turing, 236
polynomial-time, 61
reflexive transitive closure, 41, 68,
260, 320
regular
expression, 294, 302, 361
set, 9, 275, 290, 314, 319
Reingold, Omer, 29
relational composition, 310
relatively prime, 86, 87, 91
relativized complexity, 59–61,
171–174, 192–197, 210, 243
resolution, 118
resultant, 98
Rice,H.G.,227
Rice’s theorem, 227
Riemann hypothesis, 81, 90
ring of polynomials, 89, 190
Ritchie, Dennis M., 307
Rogers, Hartley, 229, 310
RP, 74, 78, 90, 186
run, 155
accepting, 156, 161
Ruzzo, Walter L., 69
S1S, 154, 283, 299
Safra, Shmuel, 116, 162, 167
SAT, 30, 33
satisfiability, 30, 33
unique, 180
Savitch, Walter, 15, 27
Savitch’s theorem, 15–16, 22, 49, 172,
279, 329, 334, 370, 372
Saxe, James, 192
Saxena, Nitin, 81, 90
Schwartz, Jacob T., 79
Schwartz–Zippel lemma, 79
scope, 131
second-order, 154
self
-correction, 121, 125
-printing program, 226–227
-reducibility, 176
-reference, 226
semantics, 128
sentence, 131
sequential composition, 306
set operator, 39
Shamir, Adi, 103
Σ
k
-machine, 57
signature, 129
simple
assignment, 259, 287, 306, 358
formula, 103, 104
set, 249, 254
simulation, 289
single-letter alphabet, 175
Sipser, Michael, 82, 112, 192
skolemization, 64, 257, 316
slowdown theorem, 312
s
m
n
function, 222, 285
Solovay, Robert, 171
sound, 387
space
bound, 11
-constructible, 14, 15, 17, 20,
281, 334
sparse, 175, 284, 349
speedup theorem, 216–219, 231, 309
abstract, 232–234
squarefree, 96
standard
basis, 126, 363
deviation, 211, 305
Stearns, Richard, 3, 4
Stockmeyer, Larry J., 44, 51, 54, 57
Streett, Robert S., 299
strongly connected, 286, 356
418 Index
successor function, 307
successor ordinal, 37
Sudan, Madhu, 116
supremum, 36, 38, 292
switching lemma, 204–210
syntax, 128
Szegedy, Mario, 116
Szelepcs´enyi, R´obert, 22
tail bounds, 211–214
Tarski, Alfred, 140
Taylor series, 213, 363, 376
t-CNF, 198
T-degree, 247, 248
t-DNF, 198
tensor product, 124
term, 130, 198, 204
ground, 130
ternary, 129
three-valued logic, 46
time bound, 11
timesharing, 245, 250, 388
Toda, Seinosuke, 180, 185
Toda’s theorem, 185–191, 301
topological sort, 295
total, 26, 259
degree, 79
order, 136
recursive function, 220
Trakhtenbrot, Boris, 216
transducer, 26, 28, 70
transfinite induction, 269, 369
transitive, 40, 276, 291, 315, 316
closure, 41
set, 36
transpose, 126
trivial, 298, 375
Turing, Alan M., 3, 4
Turing
degree, 247, 248
machine, 4
alternating, 44, 45, 51, 69,
144, 258, 293, 367
deterministic, 5, 6
nondeterministic, 7
oracle, 59
probabilistic, 74, 77
universal, 7, 17
reducibility, 236
two-counter automaton, 280
unary, 129
unassigned, 199
unbounded minimization, 287
unconditional jump, 259
undirected graph reachability, 29
unfair, 269
uniform
circuit family, 280
distribution, 77, 84
family of circuits, 66, 193, 284
logspace-, 67, 70, 374
polynomial-time, 280
union theorem, 234–235, 313
unique satisfiability, 295
universal
assignment, 258, 358
function, 222, 285
second-order formula, 257
simulation, 219
unordered tree, 80
Valiant, Leslie, 180, 186, 188
validity, 51
valuation, 130
Vazirani, Vijay V., 180, 188
verifier, 99
well-founded, 36, 37, 169, 260, 264,
266, 269, 287, 293, 358
well-ordering principle, 38
while loop, 306
while program, 306, 380
Wigderson, Avi, 101
winning strategy, 341
witness, 180, 186
yardstick, 150, 346
Zermelo–Fraenkel set theory, 38
zero divisor, 91
Zippel, Richard, 79
Zorn’s lemma, 37
TEXTS IN COMPUTER SCIENCE (continued from page ii)
Immerman, Descriptive Complexity
Jalote, An Integrated Approach to Software Engineering,
Third Edition
Kizza, Ethical and Social Issues in the Information Age,
Second Edition
Kozen, Automata and Computability
Kozen, Theory of Computation
Li and Vitányi, An Introduction to Kolmogorov Complexity
and Its Applications, Second Edition
Merritt and Stix, Migrating from Pascal to C++
Munakata, Fundamentals of the New Artificial Intelligence:
Beyond Traditional Paradigms
Nerode and Shore, Logic for Applications, Second Edition
Pearce, Programming and Meta-Programming in Scheme
Revesz, Introduction to Constraint Databases
Schneider, On Concurrent Programming
Skiena and Revilla, Programming Challenges: The
Programming Contest Training Manual
Smith, A Recursive Introduction to the Theory of
Computation
Socher-Ambrosius and Johann, Deduction Systems
Stirling, Modal and Temporal Properties of Processes
Zeigler, Objects and Systems