Papadimitriou C.H. — Computational Complexity :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Papadimitriou C.H. — Computational Complexity

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Computational Complexity

Автор: Papadimitriou C.H.

Аннотация:

Offers a comprehensive and accessible treatment of the theory of algorithms and complexity. Develops all the necessary mathematical prerequisites from such diverse fields as computability, logic, number theory, combinatorics, and probability. DLC: Computational complexity.

Язык:

Рубрика: Computer science/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1994

Количество страниц: 523

Добавлена в каталог: 11.05.2006

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

#HAMILTON PATH      441 442
#P      441 442 443 448
#SAT      442
$FP^{NP[logn]}$       423
$FP^{NP}$       416 418
$MAXSNP_{0}$       312
$NC_{1}$       386 395
$NC_{2}$       395
$NC_{i}$       376 385 396 405
$P\overset{?}{=} NP$ problem      13 45 137 148 319 329 377
$P^{NP}_{||}$       423 424
$QSAT_{i}$       427 428
$\delta$ -assignment      263
$\delta$ -BPP      263 264
$\delta$ -expander      317
$\Delta_{i}P$       424 433 434
$\epsilon$ -approximate algorithm      300
$\epsilon$ -approximate algorithm, asymptotic      323
$\mathcal{O}$ -notation      5
$\oplus P$       448 449 453
$\oplus$ MATCHING      449
$\oplus$ SAT      448 449
$\phi$ -GRAPHS      94 95 112 172
$\prod_{i}P$       424 427 433
$\sum$ — $\prod$ expression      476
$\sum_{i}P$       424 425 426 428 433
(log n,1)-restricted verifier      320
2-PARTITION      216
2SAT      184 185 398
3-Coloring      198 297
3-OCCURRENCE MAX3SAT      315 316 318
3-PARTITiON      216
3SAT      183 189 191 193 199
4-DEGREE INDEPENDENT SET      190 313 318
4-PARTITION      216
5-OCCURRENCE MAX2SAT      318
ABPP      474 475 480
AC      385 386
Accepting language      504
Adleman, L.      235 273 294 296
Advice string      277
Aho, A.V.      14 177 212 393
Akl, S.      385
AL      400 401
Aleliunas, R.      407
Alexi, W.B.      295
Algorithm      1 3 4 24
Algorithm, $\epsilon$ -approximate      300
Algorithm, approximation      300
Algorithm, Las Vegas      256
Algorithm, local improvement      303
Algorithm, Monte Carlo      244 247 253
Algorithm, NC      376
Algorithm, parallel      359
Algorithm, polynomial-time      6 11 13 137
Algorithm, pseudopolynomial      203 216 221 305
Algorithm, randomized      244
Algorithm, RNC      381
ALICE      279
Allender, E.      295
Alon, N.      353
Alphabet      19
Amplifier      316 318
Anderson, R.J.      392
Andreev, A.E.      353
Angluin, D.      452
ANOTHER HAMILTON CYCLE      232
AP      400 458
app      471
Appel, K.      180 214
Approximation algorithm      300
Approximation threshold      300–302 304 305 309
Arithmetical hierarchy      68
Arithmetization      476 507
Arora, S.      328 507 508
Arthur — Merlin game      296
ASPACE (f(n))      400
Asymptotic $\epsilon$ -approximate algorithm      323
ATIME (f(n))      400
Atomic expression      87
Average-case analysis of algorithms      7 297 298
Average-case NP-complete problems      298
Axiom      101 124
Axiom, nonlogical      104
Axiomatic method      103
Axiomatization      103
Babai, L.      296 452 507
Baker, T.      351
Balcaezar, J.L.      177 501
Bandwidth minimization      215
Barrington, D.      386
Beatles, the      439 452
Beaver, D.      488
Bennett, C.      351
Berger, B.      390
Berman, L.      326 350 503
Berman, P.      351
Bernoulli random-variable      258
Bin packing      204 323-325
Binary representation of integers      10 26 43
Binary search      228 417
Bipartite graph      11 213
Bisection width      193 211
Blass, A.      433
Block respecting Turing machine      157
Blum complexity      156
Blum, M.      156 275 296
Board games      459 460 487
Bob      279
Book, R.V.      500
Boole, G.      84
Boolean circuit      80 169 267 321 344 369 378 427 431
Boolean circuit, depth      370
Boolean circuit, monotone      86 163 170 240 344
Boolean circuit, polynomial family      268 276 431
Boolean circuit, size      267 370
Boolean circuit, variable-free      81
Boolean circuit, width      406
Boolean connectives      86
Boolean expression      73
Boolean function      79
Boolean hierarchy      434
Boolean logic      73
Boolean variable      73
Boppana, R.B.      277 353
Borodin, A.      155 405 408
Bottleneck      11
Bovet, D.P.      505
bpp      259 263 269 272 429 430 433
Brent's principle      361 363
Brent, R.P.      386
Budget B      13
Buss, S.R.      386 434
Cai, J.-Y.      295 434 436 453
Capacity      8
Capacity of a cut      16
Carry      364
Chandra, A.K.      406
Chernoff bound      258
Chinese remainder theorem      225 237
Chistov, A.L.      385
Chomsky hierarchy      66
Chomsky, N.      66
Chor, B.      295
Chordal graph      213
Christofides, N.      325
Chromatic number      214
Church, A.      51
Chvaetal, V.      323
Circuit      see “Boolean circuit”

Circuit complexity      267 268 343
CIRCUIT SAT      81 163 164 171
CIRCUIT VALUE      81 162 168 392 400
Clause      75
Clause, Horn      78 116
CLIQUE      190 344 507
CLIQUE SIZE      423
Closed under reductions      166 401 492
Cobham, A.      15
Coincidence probability      260
Communication complexity      392
Compactness Theorem      85 111
Comparator gate      390
Complement of a language      142 219
Complete problem      165 409
Complexity class      29 139
Complexity, average-case      298
Complexity, Blum      156
Complexity, circuit      267 268 343
Complexity, communication      392
Complexity, Kolmogorov or descriptive      52
Complexity, space      35
Complexity, time      29
Composition of reductions      164
Computation of a Turing machine      21 131 167
Computation table      167
Configuration      21 28 38 45 128 147 398
Configuration graph      147 398
Conjunction      73
Conjunctive normal form      75
CONp      219 235
Consistent set      105 107
Constant restriction of an optimization problem      324
Constant symbol      86
CONTEXT-FREE EMPTINESS      391
Context-free grammar      67 391
Context-free language      67
Context-sensitive grammar      66
Context-sensitive language      66
Contradiction, arguing by      105
Cook, S.A.      55 155 178 388 389 391 406 408
Cook’s theorem      171
Cook’s theorem, weak verifier version      319
Cormen, T.H.      14
coRP      256 272
Counting problem      439
Crescenzi, P.      505
CRITICAL 3-COLORABILITY      415
CRITICAL HAMILTON PATH      415
CRITICAL SAT      415
Crossing sequence      52
Crossword puzzle      211
Crude circuit      344
Cryptography      279
cryptography, public-key      280
Cryptography, randomized      286
Cubic graph      233
CYCLE COVER      211 440
Dantzig, G.B.      183 217
Davis, M.      69 136
Decision version of an optimization problem      9 13
Decoding key d      279
Deduction technique      104
default      435
DEFAULT SAT      435
Default, extension      435
Dekhtyar, M.I.      499
Dense language      336
density      336
Determinant      241 242 367
Determinant, symbolic      242
Diagonalization      60 145
Diaz, J.      177
Diffie, W.      294
Dinic, E.A.      16
Discrete logarithm      281 295
Disjoint paths      214 215
Disjunction      73
Disjunctive normal form      75
Distributed computation      481
DOMINATING SET,      208
DP      412 413 433
Dreben, B.S.      501
Dual optimization problems      222 236
Duality      222 236
Dwork, C.      388
Dyer, M.E.      452
Dymond, P.W.      178 388 389 408
e      492 500
Edge of a graph      3
Edge of a graph, undirected      188
Edmonds, J.      15—17 137 154
Eisenstein's rectangle      251
Elementary language      498 499
Elias, P.      16
Elimination of quantifiers      502
Empty string $\epsilon$       21
Encoding key e      279
Encrypted message      279
Enderton, H.B.      84 118
EQUAL OUTPUTS      234 240
Equality      86 97
Erdoes — Rado lemma      345
Euclid's Algorithm      14 252 273
EUCLIDEAN STEINER TREE      209
EUCLIDEAN TSP      210
Even, S.      487
EXACT COVER BY 3-SETS      207
EXACT TSP      411 413
Existential second-order logic      113
Existential second-order logic, Horn      176
Existential second-order logic, Krom      399
EXP      142 145 491 499 500
Expander      317
Expectation of a random variable      247
Expression, atomic      87
Expression, Boolean      73
Expression, bounded      126
Expression, first-order      88
Expression, second-order      113
EXPSPACE      497 499
Factoring      230 237
Fagin, R.      120 179
FALSE      74
False negative      244
False positive      244
Family of circuits      267
Family of circuits, uniform      269
Feasible solution      236 299
Feige, U.      507
Feigenbaum, J.      488
Feinstein, A.      16
Fenner, S.      352
Fermat test      247
Fermat witness      273
Fermat's (little) theorem      225
Finite automaton      55 56
First-order logic      87
FIRST-ORDER SAT      495
Fischer, M.J.      155 276 503
Fixpoint logic      120
Flow      8
FNP      229 230 235
Ford, L.R.      16
Fortnow, L.      352 452 488 506 507
Fortune, S.      180 214
FP      229 230 235
Fraenkel, A.S.      487
Frieze, A.M.      276 452
FSAT      228 230

1 2 3 4

О проекте