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

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

Fulkerson, D.R.      16
Full gate      379
Function problems      227
Function symbol      86
Furst, M.      387
Gabarroe, J.      177
Gabber, O.      327
Gadget      187 420
Gadget, choice      194 443
Gadget, choice-consistency      200
Gadget, consistency      195 421 445
Gadget, constraint (or clause)      197 422 444
Galil, Z.      327
Galperin, H.      500
Gap theorem      145
Garey, M.R.      172 174 176 177 181 182 207 209 212 215 216 327 487
Gate of a circuit      80
Gaussian elimination      242 272
Gauss’ Lemma      249
Genesareth, M.      436
Geography      460
Gilbert, J.R.      488
Gill, J.      274 351
Go      462
Goal K      9
Goedel on $P\overset{?}{=} NP$       179
Goedel's completeness theorem      107
Goedel's incompleteness theorem      134
Goedel, K.      119 135
Goldberg, A.V.      17
Goldfarb, W.D.      501
Goldreich, O.      296
Goldschlager, L.M.      178 391
Goldwasser, S.      295 296 507
Golumbic, M.C.      179 214
Gordreich, O.      295
Gottlob, G.      436
Graedel, E.      179 408
Graham, R.L.      174 176 181 209 210 215
Grammar      66
Graph      3 26 89 93
Graph isomorphism      291 329
GRAPH NONISOMORPHISM      291
GRAPH RELIABILITY      441
Graph theory      89 93 94 112 173 176
Graph, bipartite      11 213
Graph, chordal      213
Graph, cubic      233
Graph, interval      213
Graph, perfect      214
Graph, periodic      493
Graph, planar      210
Graph, representation      4 26
Graph, succinct      493
Graph, symmetric or undirected      93 94 188 401
Greenlaw, R.      391
Groetschel, M.      183 217 237
Grollman, J.      295
Group theory      103 136
Grzegorczyk hierarchy      357
Grzegorczyk, A.      154
Gundermann, T.      434
Gurevich, Y.      298 433
Haestad, J.      276 436
Haken, A.      236
Haken, W.      180 214
Halmos, P.      275
Halstenberg, B.      393
HALTING      59 60
Hamilton cycle      209
Hamilton path      114 193
HAMILTON PATH COMPLEMENT      219
HAPPYNET      231
Hardy, G.H.      238 277
Hartmanis, J.      55 154 350—352 434 500
Hash table      337
Hay, L.      434
Hellman, M.E.      294
Hemachandra, L.      295 351 434 453 500
Henkin, L.      108 119
Hennie, F.C.      54
Herbrand's theorem      119
Herbrand, J.      119
Hertz, J.      239 387
Heuristic      300 303
Hierarchy, arithmetical      68
Hierarchy, Boolean      434
Hierarchy, Chomsky      66
Hierarchy, exponential      498 499
Hierarchy, Grzegorczyk      357
Hierarchy, nondeterministic space      155 500
Hierarchy, nondeterministic time      155
Hierarchy, polynomial      433
Hierarchy, space      145
Hierarchy, time      145
Hilbert, D.      135
Hoover, H.J.      386 391
Hopcroft, J.E.      14 16 51 157 180 214 488
Hopfield neural net      232 239
Horn clause      78 116
HORNSAT      79 117 176 229
Huang, M.      273
Immerman — Szelepscenyi theorem      151
Immerman, N.      157 179 500
Implicant      75
IN-PLACE ACCEPTANCE      480
IN-PLACE DIVERGENCE      481
Inconsistent set      105
Independent set      188 208 210 213 307
Induction axiom      126
Inherently sequential problem      365 381 389
Integer programming      201 217 502
Interactive proof      289
Interactive proof system      289 475
Interactive proof system, multiprover      507
Interval graph      213
Inverse      367
IP      290 475 480
Isolating lemma      383
Isomorphism conjecture      351
Itai, A.      176 210
Jae Jae, J.      385
Johnson, D.S.      172—174 176 181 182 207 209 210 215 216 239 323 327 328 487
Jones, N.D.      391 406
Justified generalization      106
k-coloring      198
k-DEGREE INDEPENDENT SET      190 309
k-MAXGSAT      302
Kann, V.      326
Kannan, R.      276
Karchmer, M.      394
Karloff, H.      392 488
Karmarkar, N.      183 217 325
Karp, R.M.      16 172 178 207 277 325 385 407 437 487
Kernel      208
Khachiyan, L.G.      183 217
Kirousis, L.M.      392
Klawe, M.M.      386 394
Kleene, S.C.      51 68
Knapsack      202 203 305
Knapsack encryption scheme      294
Knuth, D.E.      14 15 181 215
Ko, K.I.      436
Koenig's lemma      85
Kolaitis, P.      180
Kolmogorov or descriptive complexity      52
Kolmogorov, A.N.      52
Kou, L.      326
Koutsoupias, E.      297
Kowalski, R.A.      84

Kozen, D.C.      406
Krentel, M.W.      434
Krog, A.      239 387
Krom clause      399
Krom sentence      399
Kumar, M.P.      16
Kurtz, S.A.      352
L      35 142 148 395 405 406
L-reduction      309
Laaser, W.T.      391 406
Ladner, R.E.      177 178 350
Lagarias, J.C.      276 294
Lame, G.      14
Landweber, L.      350
Language      24
Language, dense      336
Language, sparse      336
Language, unary      336 337
Las Vegas algorithm      256
Lautemann, C.      437
Law of quadratic reciprocity      249
Leaf language      504
Legendre symbol $(\cdot|\cdot)$       249
Leighton, F.T.      385
Leiserson, C.E.      14
Lengauer, T.      391 393 488
Lenstra, A.K.      183 217 237 295
Lenstra, H.W.      183 217 237 295
Levin, L.A.      178 297
Lewis, H.R.      51 66 84 118 408 501
Lewis, P.L. II      55 154
Li, M.      52
Liechtenstein, D.      176 210 487
Lien, E.      406
LINEAR DIVISIBILITY      236
Linear programming      201 354 502
Linear speedup      32
Lipton, R.J.      277 297 350 407 437 489
Literal      73
Logic      71
Logic programming      84 179
Logical characterization      173 176 399 435
Longest path      209
Loui, M.C.      389
Lovaesz, L.      183 217 237 295 407 507
Lowenheim — Skolem theorem      111
Lozano, A.      501
Luby, M.      390
Lund, C.      323 328 488 507 508
Lynch, J.F.      180 214
Lynch, N.A.      177
Machtey, M.      135
Mahaney, S.R.      351 352
Maheshwari, S.N.      16
MAJSAT      256
Malhotra, V.M.      16
Manders, K.      235
Markov, A.      51
Markowsky, G.      326
Master tour TSP      435
Matching      11 12 17 301 381 440
Matching, weighted      382
Matiyasevich, Y.      136
Matrix inversion      367
Matrix multiplication      360
MAX BISECTION      192 193
MAX CUT      191 303
MAX FLOW      8 12 16 365 377 378 383
MAX FLOW (D)      9 391
MAX NAESAT      318
MAX OUTPUT      416
MAX SAT SIZE      423
Max-flow min-cut theorem      9 15 221 381
MAX-WEIGHT SAT      416
MAX2SAT      186
MAX3SAT      314
Maximal independent set      389
Maximal independent set, lexicographically first      390
MAXPCP      327
MAXSAT      186 301 302
MaxSNP      312 314 318 325 327
MAXSNP-complete problems      314 322
Mayr, E.W.      391 392
McKenzie, P.      406
Megiddo, N.      174 208 239
Mental poker      289
Merkle, R.C.      294
Meyer, A.R.      155 487 503
Micali, S.      295 296
Miller, G.L.      273
MIN CUT (D)      221
MINIMUM CIRCUIT      427
MINIMUM COLORING      324 327
MINIMUM UNDIRECTED KERNEL      209 325
Minimum-weight perfect matching      382
MIP      506
Model      90 92 111 114
MONOTONE CIRCUIT VALUE      178
Monte Carlo algorithm      244 247 253
Monte Carlo algorithm for 2sat      247
Monte Carlo algorithm for compositeness      253 274
Monte Carlo algorithm for REACHABILITY      404
Monte Carlo oracle algorithm for sat      449
Mostowski, A.      68 136
Motwani, R.      328 390 508
Mulmuley, K.      392
Multilinear function      507
NAESAT      187 191
Naor, J.      390
Naor, M.      390
NC      375 385 395 405
NC algorithm      376
ne      492
Negative example      346
Network      8
Network of queues      505
NEXP      491 499
Nilsson, N.      436
Nisan, N.      406 408 488
Niven, I.      238
nl      142 148 395 398 405
Node cover      190 210 300
NODE COVER, 4-DEGREE NODE COVER      318
NODE COVER, k-DEGREE NODE COVER      310 313
Node or vertex of a graph      3
Nondeterministic Turing machine      45 171
NP      46 142 148 166 171 173 181 235 257 272 319 320 321 330 433 499
NP $\cap$ coNP      221 222 235 255 412
NP-complete problem      181 330 336 350
NSPACE(f(n))      141 147 151 153
NTIME(f(n))      47 141 147 353
Number theory      88 91 111 123 132 503
ODD MAX FLOW      377 378
Odlyzko, A.M.      294
ONE-IN-THREE SAT      207
one-time pad      280
One-way function      281 283 286
Optimization problem      221 236 299 411
Oracle      339 340
Oracle proof system      506
Oracle results      343 344 351 352 436 499
Oracle Turing machine      339 417 506
Oracle Turing machine, answer state "yes" or "no"      339
Oracle Turing machine, query state      339
Oracle Turing machine, query string      339
Oracle Turing machine, robust      353
Orlin, J.B.      489
P      46 142 148 166 168 176 235 263 268 269 272 357 385 401 405 433 499
P-complete problems      168 377 378 391
padding      491

1 2 3 4

О проекте