Kozen D.C. Theory of Computation
Подождите немного. Документ загружается.
404 Notation and Abbreviations
R real numbers......................................136
#f # size of f ...........................................141
sign(x)signofx...........................................141
S1S monadic second-order theory of successor . . . . . . . . . . 154
s successor function.................................154
SnS monadic second-order theory of n successors . . . . . . . 154
IO(σ) IO set of run σ ....................................156
PCP Post correspondence problem......................160
approximates......................................173
Σ
≤k
strings over Σ of length at most k .................178
USAT unique satisfiability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
A
⊥
orthogonal complement of A .......................181
<A> linear span of A ...................................181
codim E codimension of linear space E .....................182
#P counting complexity class..........................185
W (p, A, x) set of witnesses....................................186
PP probabilistic polynomial time . . . . . . . . . . . . . . . . . . . . . . 186
⊕P parity P ...........................................186
R operator on complexity classes.....................187
BP operator on complexity classes.....................187
P operator on complexity classes.....................187
⊕ operator on complexity classes.....................187
Σ
p
operator on complexity classes.....................187
Π
p
operator on complexity classes.....................187
Σ
log
operator on complexity classes.....................187
Π
log
operator on complexity classes.....................187
# operator on complexity classes.....................187
Notation and Abbreviations 405
N[z] polynomials with positive integer coefficients . . . . . . . 190
AC
0
circuit complexity class............................192
t-CNF t-conjunctive normal form.........................198
t-DNF t-disjunctive normal form..........................198
|M | length of a term or clause..........................198
F
X
free Boolean algebra on generators X ..............204
m(ϕ)mintermsofϕ .....................................204
var(M, C) variables occurring in both M and C ..............205
ϕ
−W
ϕ with variables in W deleted.....................205
a.e. almost everywhere.................................216
i.o. infinitely often. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
f ◦ g functional composition.............................217
< , > pairing function...................................221
π
n
i
projection function................................221
κ
c
constant function with value c .....................221
U universal function.................................222
s
m
n
s
m
n
function .......................................222
comp composition operator..............................223
pair pairing operator...................................224
const constant function operator.........................224
r.e. recursively enumerable ............................ 227
∞
∀
for all but finitely many...........................233
∞
∃ there exist infinitely many . . . . . . . . . . . . . . . . . . . . . . . . . 233
≤
T
Turing reducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
Σ
0
1
r.e. sets............................................236
∆
0
1
recursive sets......................................236
406 Notation and Abbreviations
Π
0
1
co-r.e. sets.........................................236
Σ
0
n
class in the arithmetic hierarchy...................236
Π
0
n
class in the arithmetic hierarchy...................236
∆
0
n
class in the arithmetic hierarchy...................236
EMPTY TMs accepting ∅ ..................................238
TOTAL total TMs.........................................238
FIN TMs accepting finite sets . . . . . . . . . . . . . . . . . . . . . . . . . . 238
COF TMs accepting cofinite sets . . . . . . . . . . . . . . . . . . . . . . . . 238
≤
m
many–one reducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
M(x)↓ M halts on x ......................................242
M(x)↓
t
M halts on x in t steps............................242
M(x)↑ M loops on x......................................242
M(x)↑
t
M does not halt on x for t steps...................242
REC TMs accepting recursive sets . . . . . . . . . . . . . . . . . . . . . . 244
REG TMs accepting regular sets . . . . . . . . . . . . . . . . . . . . . . . . 244
CFL TMs accepting context-free sets. . . . . . . . . . . . . . . . . . . .244
ϕ
x
(y)↓ ϕ
x
is defined on y .................................248
W
x
domain of ϕ
x
......................................248
K {x | ϕ
x
(x)↓}.......................................248
≡
m
many–one equivalence.............................248
≡
T
Turing equivalence.................................248
<
T
strict ≤
T
..........................................253
ϕ
x
(y)↓
m
halts in m steps...................................255
Π
1
1
class in the analytic hierarchy.....................257
∆
1
1
class in the analytic hierarchy.....................257
IND programming language for the inductive sets. . . . . . . 258
R
∗
reflexive transitive closure of R ....................260
Notation and Abbreviations 407
ω
1
smallest uncountable ordinal.......................263
ω
ck
1
smallest nonrecursive ordinal......................263
ω
∗
finite-length strings over ω .........................263
o ordinal labeling....................................264
f nfrestricted to domain {0, 1,... ,n−1}............265
# nondeterministic choice............................268
2SAT 2CNF satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
AFA alternating finite automaton.......................277
DFA deterministic finite automaton.....................278
NFA nondeterministic finite automaton.................281
fix fixpoint operator..................................285
k-FA k-headed finite automaton.........................291
APDA auxiliary pushdown automaton . . . . . . . . . . . . . . . . . . . . 292
BDD Boolean decision diagram..........................295
gcd greatest common divisor...........................296
π
n
k
projection function................................306
−1
reverse operator...................................310
R ◦ S relational composition.............................310
graph f graph of function f ................................310
PA Peano arithmetic..................................314
Index
#P, 185, 186, 301, 302, 378
⊕P, 186, 301
2CNF, 34, 276, 323
2SAT, 276, 323
3CNF, 34, 117, 291
3SAT, 34, 114
≤
log
m
-complete, 28
≤
log
m
-hard, 28
≤
p
m
-complete, 28
≤
p
m
-hard, 28
abstract complexity measure, 232,
311–313
acceptable indexing, 222
acceptance
alternating finite automaton, 278
B¨uchi, 156, 161, 283
IND program, 259
k-FA, 291
Muller, 161, 284
parity, 299
Rabin, 161
Streett, 299
accepting
computation history, 335, 364
subtree, 293
acceptor, 5, 6
Ackermann, Wilhelm, 308
Ackermann’s function, 308
active list, 217
additive, 121
adjacency matrix, 79
Adleman, Leonard, 90
affine function, 141
Agrawal, Manindra, 81, 90
Ajtai, Miklos, 192
α-approximation algorithm, 114
alternating
finite automaton, 277, 327
pushdown automaton, 367
Turing machine, 44, 45, 51, 69,
144, 293, 367
alternation, 44
amplification, 82–83, 101, 113, 116,
184, 296, 363, 377
analytic hierarchy, 257–262
approximation
algorithm, 114
hardness of, 114–118
ratio, 114
scheme, 114
arithmetic, 146
circuit, 79
hierarchy, 57, 236–246, 257
arithmetization, 103, 119
arity, 129
Arora, Sanjeev, 114, 116
410 Index
assignment
existential, 258, 287
simple, 259, 287, 306, 358
universal, 258, 358
asymptotic complexity, 11
atomic formula, 131
automaton
alternating, 277
auxiliary pushdown, 292, 367
B¨uchi, 155–159, 161, 283, 298,
343
finite, 9, 281, 291, 294, 302, 372
k-counter, 280
with linearly bounded
counters, 25, 275
k-headed, 26, 291, 319
Muller, 155, 157–159, 161, 347
one-counter, 280
Rabin, 155, 161, 167
two-counter, 280
automorphism, 137
auxiliary pushdown automaton, 292,
367
axiom, 134
axiom of choice, 37, 293
axioms of equality, 136
Babai, L´aszl´o, 102
back-and-forth argument, 137, 229,
364, 384
Baker, Theodore P., 171
balanced parentheses, 277, 326
Bennett, Charles, 171
Berlekamp, Elwyn, 95
Berman, Leonard, 140, 146, 151
Berman, Piotr, 175
Bernoulli trials, 211, 305
bilinear, 126
binary, 129
binary tree, 270
binomial distribution, 212
bipartite
adjacency matrix, 79
graph, 79
matching, 79
Biswas, Somenath, 81, 90
Blum, Manuel, 4, 216, 231
Blum axioms, 231
Boolean
algebra, 64, 204
free, 204, 380
decision diagram, 295
matrix multiplication, 67–68
Boppana, Ravi, 192
Borodin, Allan, 66, 216
bound occurrence, 131
bounded probabilistic polynomial
time, 74, 78
BPP, 74, 78, 82, 186
B¨uchi, J. Richard, 154
B¨uchi automaton, 155–159, 161, 283,
298, 343
determinization, 167–170
Cai, Jin-Yi, 299
Cantor,Georg,35
Cantor–Schr¨oder–Bernstein theorem,
230, 310
cardinality, 369
carrier, 128
census function, 22, 175, 177
chain, 38, 39
-continuous, 39, 292, 293, 369,
370
Chandra, Ashok K., 44, 54
Chang, Richard, 172
characteristic
function, 60, 194, 327, 374
of a field, 91, 95
string, 157
Chebyshev bound, 211, 305
checkmate, 52, 260
Chernoff bound, 199, 200, 212, 213,
305, 306
Chinese remainder theorem, 86–89,
97, 103, 106, 152
Church, Alonzo, 3, 4
Church’s thesis, 4
circuit, 31
arithmetic, 79
Boolean, 295
constant-depth, 192–210, 295
dual, 71, 194
parity, 198
Index 411
t-, 200
value problem, 30–33, 49
for constant-depth circuits,
295
clause, 198
clique, 114
clock, 13, 18, 173, 313, 385
closed, 39
closure
operator, 40
ordinal, 43, 47, 264, 293, 370
reflexive transitive, 68
CNF, 117
Cobham, Alan, 4
cofinite, 238
coinductive, 262
combinatory logic, 4
combining lemma, 312
common subexpression, 34
complete
lattice, 38, 46
partial order, 292
subgraph, 114
completely honest, 313
completeness, 28, 239–240
complexity
class, 4, 12–13
abstract, 232
inclusion, 13–15
separation, 17–20
measure, 231
abstract, 231–235
relativized, 171–174, 192–197,
210, 243
composite, 90
composition
functional, 217, 223, 306, 364
relational, 310
sequential, 306
computation
history, 147, 281
accepting, 150, 151, 245, 346,
364, 372, 374
path, 387
accepting, 378
computational complexity, 3
concatenation, 377
concurrency, 267
concurrent program, 267
conditional
expectation, 75, 115, 362
probability, 75, 127
test, 258, 259, 287, 306
lazy, 311, 358
configuration, 9, 15, 320, 368
conjunctive normal form, 34
consistent, 116
context-free
grammar, 277
language, 314
context-sensitive language, 22
Cook, Stephen, 30, 66
Cook–Levin theorem, 28, 30, 33–34,
52, 117, 335, 372
Cook reducibility, 61
Cooper, D. C., 151
countable, 38, 263
counting, 185
crossing sequence, 7, 8, 21, 319
Csanky, L., 80
CVP, 30, 33
cyclic
generator, 91
group, 91
dag, 34
De Morgan laws, 104, 117, 347
decision problem, 134
deductive system, 128
∆
1
1
, 264
DeMillo, Richard A., 79
dense, 136, 175
linear order, 135
depth-first search, 112
derivative, 96
determinant, 80
determinization
B¨uchi automaton, 167–170
finite automaton, 302
diagonalization, 17, 172, 196, 215
dictionary, 316
direct product, 86
directed graph reachability, 28
distribution
412 Index
uniform, 77, 84
distributivity, 64, 202, 204
iterated, 358
DNF, 117
domain, 128
dual, 47
circuit, 71, 194
machine, 58
dyadic second-order theory of
successor, 159–160
Edmonds, Jack, 4
effective, 223
computability, 4
Ehrenfeucht–Fraiss´e game, 135, 282,
298, 339, 375
elementary time, 154
enumeration
machine, 250
state, 250
environment, 130
equicardinality, 299
Euclidean algorithm, 87, 94, 296
Euler ϕ function, 91
event, 74, 111
existential assignment, 258, 287
expectation, 75
conditional, 75, 115, 362
linearity of, 75, 115
extended Riemann hypothesis, 81, 90
extension
finite, 96
normal, 96
factorization, 80
fair, 269
termination, 267–271, 388
fairness condition, 268
Feige, Uriel, 116
Feldman, Paul, 112
Fermat’s theorem, 90, 91
Ferrante, Jeanne, 135, 140, 151
field, 79, 80, 89, 91, 95, 180, 181, 298
finitary, 39, 292, 369
finite
automaton, 9, 281, 291, 294,
302, 372
alternating, 277, 327
k-headed, 291, 319
extension, 96
field, 79, 80, 89, 91, 95, 180, 181,
298
fingers, 25, 29, 324
injury priority argument, 247,
253, 254
first-order
induction, 257
logic, 128
theory, 133, 282, 298
Fischer, Michael J., 140, 146, 147, 151
Fischer–Rabin trick, 147, 149
fixpoint, 39, 224, 226, 285, 352, 384
combinator, 224
least, 258, 261
lemma, 224
for
loop, 306
program, 306, 383
forced win, 53
formula, 129, 131
atomic, 131
Fortnow, Lance, 103
Fortune, Steven J., 175
free
Boolean algebra, 204, 380
occurrence, 131
Friedberg, R. M., 247, 253
Friedberg–Muchnik theorem, 247,
253–256
full tree, 271
function
bilinear, 126
characteristic, 60, 194
µ-recursive, 4
pairing, 238
primitive recursive, 306–308
productive, 249, 251
functional
abstraction, 46
composition, 217, 223, 306, 364
Furst, Merrick, 192
Galois
field, 92
group, 96
Index 413
game, 135
complexity of, 52–56
two-person perfect information,
52, 260
gap theorem, 216, 231, 312, 359
abstract, 232
Gaussian elimination, 97
gcd, 96, 296, 362
generic complete problem, 58
geography, 53
generalized, 54, 277, 326
Gill, John, 171
G¨odel, Kurt, 3, 150, 287, 306, 359
G¨odel numbering, 17, 222, 226
Goldreich, Oded, 101
Goldwasser, Shafi, 102, 112, 116
graph isomorphism, 101
graph reachability
directed, 28
undirected, 29
greatest common divisor, 96, 267,
296, 362
integer, 67
polynomial, 67
greatest lower bound, 38
greedy algorithm, 115, 297
ground term, 130
group, 129, 134
of units, 91
halting, 5, 259
halting problem, 242, 247
hardness, 28, 239
Harel, David, 258, 269
Harel’s theorem, 269–271
Hartmanis, Juris, 3
helpful direction, 269
Hennie, F. C., 4
hierarchy
analytic, 257–262
arithmetic, 57, 236–246
polynomial-time, 57–65, 192, 236
homomorphism, 87, 292
Boolean algebra, 204
monoid, 160
nonerasing, 292
Huang, Ming-Deh, 90
hyperarithmetic relation, 263
hyperelementary, 316
relation, 258, 262–264, 266
H˚astad, Johan, 192, 204
ideal, 87
image, 120
Immerman, Neil, 22
Immerman–Szelepcs´enyi theorem, 19,
22–24, 176
immune, 249, 308
inclusion–exclusion principle, 77, 182
incompleteness theorem, 150, 224
IND program, 258, 264, 287, 316, 357
running time, 264
independence, 38, 75, 76, 305
pairwise, 76
index, 222
induction, 293
first-order, 257
principle, 35, 293
transfinite, 37
inductive
definability, 258
relation, 258, 261, 264
infimum, 38, 292
infix, 130
information order, 46
injury, 255
inner product, 120, 181, 184
integer
addition, 151–153
division, 148, 149
gcd, 67
interactive proof, 99–127, 296
invariant under finite modifications,
313
invertible, 294
IO set, 156
IP, 99, 101
IP = PSPACE, 103–112
irreducibility test, 95
irreducible, 96
isomorphism
local, 136
ring, 86
tree, 80
414 Index
isomorphism theorem, 310
Myhill, 230, 310
Rogers, 229–230, 310
iterated distributivity, 358
Johnson, David S., 115
Jones, Neil D., 27
jump operation, 286
Karloff, Howard, 103
Karp, Richard, 30
Karp reducibility, 27
Kayal, Neeraj, 81, 90
k-CNF, 34
k-counter automaton, 280
with linearly bounded counters,
25, 275
kernel, 87, 120
k-headed automaton, 26, 291, 319
Kleene, Stephen C., 3, 224, 257, 264
Kleene’s theorem, 257, 264, 358
Knaster–Tarski theorem, 41–43, 47,
53
K¨onig’s lemma, 165, 169, 388
Kozen, Dexter C., 44, 258
Kronecker product, 124
labeling, 46
Ladner, Richard, 30, 350
λ-calculus, 4
Las Vegas algorithm, 95
lattice, 38, 46
law of sum, 74, 122, 201, 207, 208,
363
lazy, 311
leaf, 264
least fixpoint, 258, 261
least upper bound, 38
Levin, Leonid, 30
Lewis, Philip, 4
lexicographic order, 168, 299, 362
limit ordinal, 37, 369
linear, 121
arrangement, 138
order, 136
speedup, 12
subspace, 181
linearity test, 120, 125
Lipton, Richard J., 79
literal, 198, 276, 291
local
consistency, 32
isomorphism, 136
logical consequence, 134
logspace, 25–29
computable function, 27
reducibility, 27
transducer, 26, 70, 296, 323
-uniform, 67, 70, 374
loop-free, 259, 260, 262
Lov´asz, L´aszl´o, 79, 116
low, 254
L¨owenheim–Skolem theorem, 136
lower bound, 7, 146–150, 192, 198–204
Lund, Carsten, 103, 116
Mahaney, Stephen R., 175, 299
Mahaney’s theorem, 177–179, 299
majority, 83
Markov bound, 211, 213, 305
matching
bipartite, 79
perfect, 79
matrix
adjacency, 79
multiplication
Boolean, 67–68
MAX-3SAT, 114, 297
MAX-CLIQUE, 114, 297
maximum clique, 298, 362
MAZE, 28, 323, 332, 336
maze, 295
McCreight, Edward M., 234
McNaughton, Robert, 162
m-degree, 247, 248
mean, 211
membership problem, 239
Meyer, Albert R., 51, 234, 307
Micali, Silvio, 101, 102
Miller, Gary, 81, 90
Miller–Rabin test, 81, 90
minimal program, 227–228
minterm, 204, 303, 304, 380
model, 133
modular arithmetic, 86, 94, 152