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

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

Padding function      333
Palindrome      23 51 55
Palmer, R.G.      239 387
Papadimitriou, C.H.      14 51 174—183 208 210 212 215 217 218 239 273 297 326 328 389 393 408 433—436 452 488 501
Parallel algorithm      359
Parallel computation thesis      389 398
Parallel computer      359
Parallel time      360
Parseval's theorem      265 275
Parsimonious reduction      441
Partition      217
Paul, W.J.      157 353 394
PCP(log n,1)      320 327
Pebble game      487
Perfect graph      214
Periodic graph      483
PERIODIC GRAPH COLORING      483 486
PERIODIC NOT-ALL-EQUAL SAT      486
PERIODIC SAT      485
Periodic scheduling      483
Permanent      440 443 448 488
PERMANENT MOD 2      449
Ph      425 428 429 433
Pippenger, N.      276 353 386 389 394
Planar graph      210
PLANAR SAT      210
PLS      329
Plucking      345
Plumstead, J.      276
Poisson random variable      469
polyL      405
Polynomial circuits      267 269 277 352 431
Polynomial circuits, uniformly      269
Polynomial composition left      154
Polynomial composition right      154
Polynomial hierarchy      424 433
Polynomial hierarchy, collapse of      427 431
Polynomial isomorphism      332
Polynomial-time algorithm      6 11 13 137
Polynomial-time approximation scheme      307 311 321 322
Polynomial-time approximation scheme, fully      307
Polynomial-time reduction      329
Positive example      346
Post, E.      51
Post’s correspondence problem      67
PP      256 257 448
PRAM (parallel random access machine)      371 374
PRAM (parallel random access machine), variants      387 388
Pratt's theorem      222
Pratt, V.R.      238 388
Prefix sums      363
Prenex normal form      99 100
Prime number      222
Prime number theorem      277
PRIMES      222 235 253 273 274
Primes, distribution of      277 286 477
Primitive root      224
Probabilistic alternating Turing machine      471
Probabilistic method      270 317 430
Probabilistically checkable proof      320 327
Product construction      307
Proper complexity function      140
Protocol      287
Pseudopolynomial algorithm      203 216 221 305
Pseudorandom number generators      276 295
PSPACE      142 148 150 340 429 433 456 458 460 471 475 499
PT/WK(f(n),g(n))      370 373 375
QSAT      455 456 458 475
Quantifier      88 90 97 425 457 471 501
Quantifier, bounded      126
Quantifier, second-order      114
R      63 499
Rabin, M.O.      15 154 273 503
Rackoff, C.      296 407
Rajogopalan, S.      298
Ramachandran, V.      385 389
Random access machine (RAM)      36
Random access machine, configuration      38
Random access machine, function computed by a      39
Random access machine, input      38
Random access machine, instructions      37
Random access machine, parallel (PRAM)      371 374
Random access machine, program counter      37
Random access machine, time spent by a      39
Random NP-complete problems      298
Random oracle hypothesis      351
Random source      259
Random source, $\delta-$       261
Random source, slightly      261
Random walk      245 272 402 407
Randomized algorithm      244
Randomized cryptography      286
Razborov's theorem      344
Razborov, A.A.      353
Re      63
Reachability      3 40 49 112 114 120 162 362 398 500
Reachability method      147 149 151 398
REACHABILITY, undirected      401 407
REACHABLE DEADLOCK      482
Reckhow, R.A.      55
Recursion theorem      68
Recursive function      24
Recursive language      24 59—61 63
Recursively enumerable language      24 59 61 63
Recursively inseparable languages      63
Reducible      160
Reduction      12 59 60 160 177 268
Reduction, Cook      177
Reduction, Karp      177
Reduction, L-      309
Reduction, logarithmic-space      160 177
Reduction, nondeterministic or $\gamma-$       235
Reduction, parsimonious      441
Reduction, polynomial-time      177 329
Reduction, randomized      449
Reduction, truth-table      177
Reduction, Turing      177
Register minimization      157 488
Regular expression equivalence      503 504
Regular language      54 503
Reif, J.      488
Reischuk, R.      388 393
Reiter, R.      436
Rejecting language      504
Relation symbol      86
Residue      224
Resolution      85 236
Rice's theorem      62
Riemann hypothesis      273
Riemann witness      274
Rivest, R.L.      14 294 296
RL      402 405
RNC      381 385
RNC algorithm      381
Robertson, E.      350
Robertson, N.      180 215
Robinson, J.A.      86
Robinson, R.M.      136
Rogers, H.      69 433
Rompel, J.      390 506
Root of a polynomial      226 243
Royer, J.S.      352
RP      254 256 267 272
RSA encryption scheme      282
Russell, B.      135
Ruzzo, W.L.      388 391 407 408
s — m — n theorem      67
Safra, S.      328 507
Santha, M.      275
SAT      77 171

SAT COMPLEMENT      219
SAT-UNSAT      413
Satisfiable expression      76 95
Savage, J.E.      277
Savitch, W.J.      157 388
Savitch’s theorem      149 457
Saxe, J.      387
sc      405
Schaefer, T.J.      487
Schaeffer, A.A.      239
Schnorr, C.P.      239 295
SCHOENFINKEL — BERNAYS SAT      496
Schoenfleld, J.R.      118
Schoening, U.      350 352
Schrijver, A.      14 181 183 215 217 218 237
Schwartz, J.T.      273 488
Search algorithm      4 40
Search algorithm, breadth-first      5 11
Search algorithm, depth-first      5 40
Second-order logic      113 173 176
Seiferas, J.      157
Seiferas, J.I.      155
Self-reducibility of SAT      228 239 302 337 431
Selman, A.L.      177 295
Semantic class      255
Serna, M.J.      392
Set covering      201 323
Set PACKING      201
Sewelson, V.      434 500
Seymour, P.D.      180 215
Shamir's Theorem      475
Shamir, A.      276 294 296 488
Shannon, C.      86
Shanon, C.E.      16
Sharir, M.      488
Shaw, R.A.      391
Shepherdson, J.C.      54 55
Sideri, M.      436
Signature      288
Silvestri, R.      505
Simple expression      475
Sink      8
Sipser, M.      56 179 277 296 351 353 387 393 437 487 506
Skolem, T.      119
SL      405 408
Slightly random source      261
SNP      311
Solovay, R.      273 351
Sound and complete proof system      86 107
Soundness Theorem      107
Source      8
Space complexity      35
Space hierarchy theorem      145
SPACE(f(n))      35 141 147 151 157
Sparse language      336
Speedup linear      32
Speedup theorem      156
Spira, P.M.      386
Spirakis, P.      392
SSAT      470 472
Standard flow      378
Staples, J.      391
Stearns, R.E.      54 55 154
Steiglitz, K.      14 183 218 237
Steiner tree      209 326
STOCHASTIC SCHEDULING      470 472
Stockmeyer, L.J.      120 176 210 387 388 406 434 487 503
Strassen, V.      273
Sturgis, H.E.      55
Subgroup      253
Subramanian, A.      391
Substitutible      98
Substitution      97
Successor relation      174 176
SUCCINCT 3SAT      493
SUCCINCT BISECTION WIDTH      493 494
Succinct certificate or witness      182
SUCCINCT CIRCUIT SAT      493 494
SUCCINCT CIRCUIT VALUE      493
Succinct graph      493
SUCCINCT HAMILTON PATH      493 494
Succinct input representation      493
SUCCINCT NON-EMPTINESS      500
SUCCINCT REACHABILITY      500
Sudan, M.      328 508
Sunflower      345
Swart, E.R.      354
Symmetric Turing machine      407
Symmetry      94
Syntactic class      255 505
System of communicating processes      481
Szegedy, M.      328 507 508
Szelepcsenyi, R.      157
Szemeredi, E.      353 408
Szwarcfiter, J.L.      176 210
Tardos, E.      17
Tarjan, R.E.      17 487 488
Tarski, A.      136
TAXICAB RIPOFF      209
Tchebychef’s theorem      278
Term      86
TFNP      230 235
THEOREMHOOD      102 133
THEORY OF REALS      503
THEORY OF REALS WITH ADDITION      502
THRESHOLD SAT      274
Tiling      501
Time complexity      29
Time hierarchy theorem      145
TIME(f(n))      145 147 157 353
Toda, S.      452
Toda’s theorem      448 452
Tompa, M.L.      408
Toraen, J.      501
Total functions      230
Tour      13
Tournament      208
Trahan, J.      389
Trakhtenbrot, B.A.      15 155
Transitive closure      212
Transitive reduction      212
Transitive reduction, strong      212
Trapdoor function      286
Trapdoor predicate      286
Traveling salesman problem (TSP)      13
Tree rooted      85
Triangle inequality      305
TRIPARTITE MATCHING      199
Trotter, W.T.      353
TRUE      74
Truth assignment      74
Truth assignment, satisfying      74
TSP      12 47 198 304 325 354 411 418
TSP (D)      198
TSP COMPLEMENT      412
TSP COST      411
Turing machine      19
Turing machine, accepting a language      24
Turing machine, accepting state “yes”      19
Turing machine, alternating      354 399
Turing machine, blank symbol $\sqcup$       19
Turing machine, block respecting      157
Turing machine, configuration      21 28 45 128 147
Turing machine, cursor      19 21
Turing machine, cursor directions $\rightarrow$ , $\leftarrow$ and —      19
Turing machine, deciding a language      24 45 400
Turing machine, first symbol $\rhd$       19
Turing machine, halting state h      19
Turing machine, nondeterministic      45 171
Turing machine, oblivious      54

1 2 3 4

О проекте