Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms
Подождите немного. Документ загружается.
Index 303
cryptographic assumptions 158
cryptography 18, 30
CSL 187
cubic 282
CVP see circuit value problem
D´ıaz 10
decision problem 29
depth-first search 197
derandomization 66, 104, 212
determinant 199
DFS see depth-first search
DHC 14, see also Hamiltonian circuit
problem
DHC
sym
see HC
DHP see directed Hamiltonian path
problem
Dietzfelbinger 68
Dijkstra 20
directed Hamiltonian path problem 78
directed s-t-connectivity 197
discrepancy 244
disjointness test 227
disjunction 17
disjunctive (normal) form 17, 260
distributional communication complex-
ity 243
division function 273
DNA-computer 20
Droste VI, VII
DTAPE(s(n)) 186
dynamic programming 94
easy
NP- 106
edge cover problem 15, 68
EdgeCover see edge cover problem
EP 28, 30
EQ
∗
229
EQ
∗
n
269
equality test (EQ) 224
Erd˝os 242
error-correcting code 165
error-probability 29
essentially dependent 252
evaluation problem 13
event 283
exor see parity
EXOR-gate 252
EXOR-nondeterminism 233
expected optimization time 117
expected polynomial time see EP
expected value 286
explicitly defined 252
exponential 282
exponentially small 283
FAC T see factoring
factoring 18, 128
failure-probability 28
fan-in 259
Feige 164
Fermat’s Last Theorem 4
fingerprinting technique 239
flow 16, see also network flow problem
fooling set 226
forcing component 80, 82
formula 208
quantified Boolean 189
formula size 254
FPTAS see fully polynomial-time
approximation scheme
Frens VII
fully polynomial-time approximation
scheme 102
function evaluator 167, 171
G¨ulich 17
Gabarr´o10
gadget 51
Gambosi 10, 114, 164
game 190
gap technique 106, 173–175
Garey 10, 56, 74, 95, 128, 190
gate 201
gate elimination 253, 254
GC see graph colorability problem
geometric distribution 293
geometric rectangle 224
GraphIsomorphism see graph
isomorphism problem
Giel VI
go 190
golden computation path 212, 241
Goldmann 265
Goldreich 27, 164
Goldsmith VII
Goldwasser 145, 164
304 Index
grammar 41
context free 41
graph coloring problem 82, 109, 143,
178
graph isomorphism problem 81, 128
greater than (GT) 224
Gronemeier VII
Grotefeld 3, 22
growth rate 279, 281
guess 39
guess and verify 69
H˚astad 175
Hadamard matrix 229, 245
Hajnal 265
Halld´orsson 103
Hamiltonian circuit problem 49,
56, 107, 158, see also traveling
salesperson problem
Hamiltonian path 78
Hamiltonian path problem 78
Hamming distance 122
handball 17
hard see also C-hard
NP- 106
hardware 201
hash function 152, 241
H˚astad 261
HC 14, see also Hamitonian circuit
problem
help 206
hockey 17
Hofmeister VI, 17
Homer 10
Hopcroft 3, 10, 19, 22, 187
HP see Hamiltonian path problem
Hromkoviˇc 10, 105
I don’t know 28
IBDD see indexed BDD
Immerman 9, 193, 197
inapproximability 108
independent events 27, 285
independent random variables 286
independent set 16
independent set problem 16, 47, 52,
68, 81, 111
indexed BDD 269
indirect storage access 256, 268
inductive counting 195
inner product 227, 265, 273
input tape 186
interactive proof system 147
inverse function 273
investment advisers 37
IP 147
IP see inner product
IS see independent set problem
ISA see indirect storage access
isomorphism
graph 81
J¨agersk¨upper VII
Jansen VII
Johnson 10, 56, 74, 95, 103, 104, 128,
190
k-dimensional matching 83
k-dimensional matching problem 16,
178, 198
k-DM see k-dimensional matching
problem
K¨obler 143
Kann 10, 114, 164
Karmarkar 104
Karp 46, 104
Karpinski 265
Kayal 68, 128
Kirchhoff rule 16
knapsack problem 15, 47, 68, 78, 80,
94, 105, 116
Knapsack see knapsack problem
Kranakis 10
Kushilevitz 10, 235, 259
l’Hospital 281
Ladner 129
language 29
large number problems 93
Las Vegas algorithm 28
law of total probability 285
Lawler 14, 15, 90
layer depth 268
LBA problem 193
ld see layer depth
length of a branching program 209
Lenstra 14, 15, 90
Levin 71
linear 282
Index 305
linear bounded automaton 193
linear programming 128
linearity test 167, 168
literal 17
local replacement 51, 56
log-space complete 196
log-space reduction 196
logarithmic 282
logarithmic cost model 20
logarithmic reduction 196
LOGSPACE 196
Long(L) 191
Lov´asz 164
lower bound 3, 21, 24, 25, 223
Lund 164
Maass 265
MADD see multiple addition function
Magnanti 16, 49
MAJ see majority function
majority function 263, 273
majority vote 33
Marchetti-Spaccamela 10, 114, 164
Markov Inequality 31, 290
Markov process 124
marriage problem 16, 53, 198
Martello 15
mask technique 229
Max-2-Sat 178
Max -3- Sat 161, 173, 177, 178, 184
Max -k- Sat 161, 178
maximization problem 99
maximum weight satisfiability 113
Max-NPO 112
Max-Sat 47
Mayr 10, 164
Micali 145
middle bit of multiplication 230, 247
Miller 128
Miltersen 66
minimal circuits 132
minimax principle 118, 244
Minimax Theorem 119
minimization problem 99
minimum spanning tree 78
Min-NPO 112
minterm 260
modified threshold circuit 266
MOD
m
-gate 263
monochromatic 225
monomial 17
monotone Boolean function 254
monotone circuits 254
monotone projection 272
Monte Carlo algorithm 28
Motwani 6, 10, 19, 22, 164, 187, 242
multiple addition function 273
multiplication function 273
multiprocessor systems 10
NC
1
-reduction 271
NC
k
272
Nechiporuk 255
needle in the haystack 121
network flow problem 16, 49, 53
neural nets 252
NetworkFlow see network flow
problem
Nielsen 21
Nisan 10, 235, 259
non-adaptive 162
non-uniform 220
nondeterminism 39
nondeterministic Turing machine 39
NP 39
NP-complete 96
strongly 93, 94, 96
NPO 112
NTAPE((s(n)) 186
number theory 18, 128
O see big O notation
OBDD see ordered BDD
oblivious 71, 204
Ogihara 10
one-sided error 29, 34, 61
one-way function 157
opponent 118
OR-gate 252
OR-nondeterminism 233
oracle 45, 130
oracle class 127
order of magnitude 279
Orlin 16, 49
outcome of a random experiment 283
output tape 196
Owen 243
P 26, 40
306 Index
padding technique 191
pairwise disjoint 283
pairwise independent 286
Papadimitriou 10
parallel computation 10
parallel computation hypothesis 195,
204, 206
parity 17
parity function 260, 265, 273
Partition 52, 80, 81, see partition
problem
partition problem 15
path
computation see computation path
path function 122
Paul 146
PCP Theorem 8, 10, 164
PCP(r(n),q(n)) 162
pebbling algorithm 103
perfect matching 198
permanent 198, 199
perpetual motion machines 2
PH see polynomial hierarchy
pigeonhole principle 211
Π
k
-circuit 260
Pinedo 15, 90
planar graph 90
polylogarithmic 282
polynomial hierarchy 8, 127, 132
polynomial reduction 60, 61
polynomial-time approximation scheme
102
polynomial-time many-one reduction
see polynomial reduction
polynomial-time reduction see
polynomial reduction
polynomially bounded 282
polynomially equivalent 60, 64
polynomially self-reducible see
self-reducible
polynomially small 283
population 117
PP 33, 40
Pr¨omel 10, 164
primality testing 18, 30, 33, 68, 93,
128, 158
Primes see primality testing
private coins 240
probabilistic method 242, 261
probabilistic proof-checker 162
probabilistically checkable proofs 161
probability 23
probability amplification 31
probability space 286
problem
algorithmic 6
approximation 10, 17
decision 21, 35, 46
evaluation 35, 46
maximization 182
minimization 182
optimization 33, 35, 46
search 13, 21, 33
product graph 176
projection 271
proof verifier 167
Protasi 10, 114, 164
protocol length 220
protocol tree 220
randomized 233
prover 146
pseudo-polynomial 95
PSPACE 186
PTAS see polynomial-time approxi-
mation scheme
PTAS reduction 110
public coins 240
Pudl´ak 265
QBF see quantified Boolean formula
quadratic 282
quality of a solution 33
quasi-linear 282
quasi-polynomial 282
query 130
QuickSort 27, 28
Rackoff 145
Raghavan 6, 242
random bit 27
random polynomial time see RP
random polynomial time with one-sided
error see RP
random variable 285
randomization 7, 39
randomized protocol tree 233
randomized search heuristic 115, 116
rank lower bound method 228
Index 307
Razborov 254, 262, 263
read-once projection 271
read-only 186, 205, 206
reciprocal function 273
rectangle 225
rectangular reduction 229
recursive see computable
reduction 7
register machine 19, 21, 22
restriction 52, 56
Rinnooy Kan 14, 15, 90
RP 29, 32, 40
RP
∗
32, see also NP
s-oblivious branching program 269
s-t-connectivity 197
Safra 164, 175
sample space 283
Sat 17, 51, 68, 72, 79, 103, 111, see also
satisfiability problem
Sat
cir
17, 137, see also Sat
satisfiability see Sat
satisfiability problem 17, 137, 164, 173,
178, 198, 214
satisfiability problem of level k 137
satisfiable 17
Sat
k
cir
137, 188
Sauerhoff VI
Savitch 9
Savitch’s Theorem 192
Saxena 68, 128
scalar product see inner product
Sch¨onhage 3, 22
Sch¨oning 143
Schaefer VII
scheduling problem 15
Schmitt 17
search tree 120
self-improvability 176
self-reducible 214–216
sequencing with intervals 80, 95
set cover problem 85, 103, 178
SetCover see set cover problem
#P 198
#P-complete 199
Shmoys 14, 15, 90
SI see subgraph isomorphism problem
Σ
k
-circuits 260
similar
algorithmically 43, 45, 61
complexity theoretically 43
simple see C-simple
Singh 4
Sipser 10, 56
size of a branching program 209
Smolensky 264
soccer 17, 55, 92
Socrates 8
software 201
Solovay 30, 68
solution
to an approximation problem 99
sorting 20
space constructible 192
space-bounded complexity 186
specification 17
Spencer 242, 261
SQU see squaring function
squaring function 273
s-t-DHP 78
Steger 10, 164
Stinson 18
Stirling’s formula 236
Stone 128
Storch VII
Strassen 5, 30, 68
strictly exponential 282
strictly exponentially small 283
strongly NP-complete 108
strongly NP-hard 108
structural complexity 8, 10, 185
subexponential 282
subfunctions 252
subgraph isomorphism problem 81
subset sum problem 78, 79, 95
SubsetSum see subset sum problem
Sudan 164
superpolynomial 282
surveillance problem 15
SWI see sequencing with intervals
Switching Lemma 261
Szegedy 164, 265
Szelepcs´enyi 9, 193, 197
T
n
≥k
253
T
n
≤k
253
team building 16
threshold circuit 264
308 Index
threshold function 253
threshold gate 264
time see runtime
top-down programming 45
Tor´an 143
total probability
law of 285
Toth 15
tournament 27
trap 122
traveling salesperson problem 14, 48,
49, 67, 94, 99, 105, 107, 116, 178
TSP 14, see also traveling salesperson
problem
TSP
∆
14, see also traveling salesper-
son problem
TSP
d-Euclid
14, see also traveling
salesperson problem
TSP
N
14, see also traveling salesper-
son problem
TSP
105
Turing equivalent 45, 49, 63
Turing machine 21, 45, 71, 113, 186
non-uniform 203, 206
oblivious 96, 204
one-tape 223
randomized 27, 39
two-tape 223
Turing reduction 45, 61
Tur´an 265
two-person zero-sum game 118
two-sided error 29
Ullman 3, 10, 19, 22, 187
unbounded-error probabilistic polyno-
mial time 33, see PP
unfold 207
uniform 203
uniform cost model 20
unimodal function 116
unit cost model 22, 279
upper bound 3, 21, 24, 25
utility 15
Valiant 199
value
of a game 119
of a solution 99
van Leeuwen 10
van Melkebeek VII
verification problem 17
verifier 146
vertex coloring 81
vertex cover problem 15, 47, 52, 68,
103, 105, 112, 178
Vetter 3, 22
Victoria 146
VLSI circuits 219, 223, 246
volleyball 17
von Neumann 119
VertexCover see vertex cover
problem
Wagner 10
Wechsung 10
Wegener 6, 10, 17, 72, 254, 255
Witt VI
word problem 191
work tape 186
worst-case approximation ratio 100
worst-case expected runtime 27, 28
worst-case runtime 23, 26
Yao 4, 118, 244
zero-error see ZPP
zero-knowledge proofs 155
zero-knowledge property
perfect 155
under cryptographic assumptions
158
zero-sum game 243
ZPP 28–30, 32, 40
ZPP
∗
32