Du D.-Z., Ko K.-I. — Theory of computational complexity :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Du D.-Z., Ko K.-I. — Theory of computational complexity

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

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

Название: Theory of computational complexity

Авторы: Du D.-Z., Ko K.-I.

Аннотация:

Du and Ko present the fundamentals of complexity theory, including NP-completeness theory, the polynomial-time hierarchy, relativization.
The book...is a graduate text...however, it can also be used profitably by researchers in theory...the selection by the authors of the book under review is excellent

Язык:

Рубрика: Математика/

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

ed2k: ed2k stats

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

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

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

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

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

# $P^{A}$       344
#3-Sat      325
#CC      328
#HC      348
#P      323
#P-compIete function      325
#SAT      322 325 388
#SS      348
#VC      326
$(\frac{x}{n})$       291
$(\frac{x}{p})$       291
$accept_{M}(x)$       293
$AC^{i}$       216
$AM^{X}_{k}$       388
$AM_{k(n)}(c)$ -complementary predicates      388
$AM_{k}(r)$ -complementary predicates      365
$AM_{r(n)}$       362
$A^{n}$       4
$A_{=n}$       198
$A_{\leq n}$       198
$BPP^{a}$       310
$BPP_{c}$       298
$CS_{A}(n)$       199
$CS_{t, A}(n)$       199
$C^{n}_{d}$       240 346
$C_{A}$       254
$C_{t}(f)$       196
$DP_{n}$       108
$D_{0}(f)$       7 151
$D_{1}(f)$       6 151 240
$err_{M}(x)$       294
$expecttime_{M}(x)$       295
$FBPP^{NP}$       350
$FP^{C}$       62
$FP^{g}$       62
$F\Delta^{P}_{3}$       350
$f^{n}_{d}$       240 346
$f_{con}$       148 238
$f_{SAT}$       119
$f|_{r}$       6
$GColor_{k}$       109
$halt_{M}(x)$       293
$H^{P, X}_{k}$       351
$H^{P}_{k}$       351
$IP_{k}$       361
$IP_{k}(q(n), r(n))$       373
$k_{a}$       125 136 314
$L^{P, X}_{k}$       351
$L^{P}_{k}$       351
$MA_{k}(r)$ -complementary predicates      365
$MA_{r(n)}$       362
$MOD_{k}$ function      213
$M^{A}$       78
$M^{f}$       60 77
$M_{(x, i)}$       26
$M_{U}$       25
$M_{x}$       24
$NC^{1}$       279
$NC^{2}$       276
$NC^{i}$       216
$NP(\mathcal{C})$       78
$NP^{A} \cap coNP^{A}$       135
$NP^{A}$       78
$NP^{A}_{b}$       129
$NP^{\mathcal{C}}$       78
$parity_{A}(x)$       334
$P^{B}$       62
$P^{\mathcal{C}}$       62
$P^{\mathcal{F}}$       324
$p_{f}$       157
$QR_{n}$       116 356
$QR_{p}$       302
$reach(\alpha, \beta, \kappa)$       92 382
$reject_{M}(x)$       293
$RP^{A}$       310
$R^{+}_{p, \mathfrak{B}}$       240
$r_{p}$       223
$Sat_{k}$       85 204
$space^{A}_{M}(x)$       63
$Space_{M}(x)$       18 19 91
$s_{M}(n)$       18 19 91
$S_{n}$       158
$TH_{m, n}$       198
$time^{A}_{M}(x)$       62 78
$Time_{M}(x)$       18 19 90 295
$t^{A}_{M}(n)$       62 78
$t_{M}(n)$       18 19 78 90
$UP^{A}$       139
$v^{*}_{\Pi}(x)$       434
$v_{\Pi}(y)$       434
$Z^{*}_{n}$       114 291
      207
$\chi_{L}$       18
$\chi_{n, A}$       198
$\Delta$       14
$\delta$ -closeness, to a multilinear function      399
$\delta$ -closeness, to a polynomial function      401
$\Delta(f, g)$       399
$\Delta^{*}$       165
$\Delta^{L}_{d}(f)$       416
$\Delta^{P}_{n}$       79
$\Delta^{\phi}$       172
$\Delta_{d}(f)$       416
$\Delta_{ml}(f)$       404
$\delta_{nl}(f)$       404
$\equiv^{p}$       246
$\exists^{+}$       307 336
$\exists^{+}_{r}$       306 365
$\hat{t}_{M}(n)$       295
$\iota$       5 24
$\lambda$       4
$\langle x,y\rangle$       5
$\langle\langle ...\rangle\rangle$       278
$\leq^{log}_{m}$       218
$\leq^{NC^{1}}_{m}$       279
$\leq^{NP}_{T}$       78
$\leq^{P}_{1tt}$ -completeness      275 282
$\leq^{P}_{1}$       247
$\leq^{P}_{2tt}$ -completeness      269
$\leq^{P}_{c}$       256
$\leq^{P}_{d}$       256
$\leq^{P}_{inv, li}$       247
$\leq^{P}_{inv}$       247
$\leq^{P}_{ktt}$       256
$\leq^{p}_{m}$       47 430
$\leq^{P}_{pos-T}$       73
$\leq^{P}_{tt}$       73 256
$\leq^{P}_{T}$       58 62
$\leq^{S N P}_{T}$       108
$\leq_{T}$       58 62
$\mathcal{C/F}$       202
$\mathcal{c}$ -approximation, by a Boolean circuit      236 345
$\mathcal{C}$ -hard problem      63
$\mu$       132
$\mu(f)$       157
$\neg$       5
$\Omega(f(n))$       39
$\omega(G)$       433
$\oplus P$       334
$\oplus P^{A}$       344
$\oplus$       6
$\oplus(A)$       334
$\otimes$       426
$\overline{GIso}$       see "Graph Nonisomorphism"
$\pi$       64
$\Pi^{P}_{2}$ -complete set      88
$\Pi^{P}_{k}$       79
$\Pi^{P}_{k}$ -predicate      80
$\sigma$ -field      132
$\Sigma^{P, A}_{1}$       108

$\Sigma^{P}_{k}$       79
$\Sigma^{P}_{k}$ -complete set      85
$\Sigma^{P}_{k}$ -predicate      80
$\varphi (n)$       114
$\varphi M$       323 340
$\vDash$       9
$\vdash^{no}$       61 81
$\vdash^{yes}$       61 81
$\vdash_{M}$       9
$\vee$       5
$\wedge$       5
$\wr$       175
( $NP \cap coNP$ )-complete set      116
(a, b)-acceptance      234
(Clique, r-Noclique)      433
(n, d, $\delta$ )-expander      439
(SAT, r-Unsat)      394 431
1-Factor      188
1-IN-3-3SAT      72
2-Approx-3Sat      433
2-SAT      72
3-CNF- $Sat_{k}$       87
3-Dimensional Matching (3DM)      72
3-DNF- $Sat_{k}$       87
3-QBF      96
3-SAT      50 249
3DM      see "3-Dimensional Matching"
3Sat-3      438
A-reducibility      449
Aanderaa      192
Adjacency matrix      45 148
Adleman, L.      112 319
Adversary argument      154
Affine subspace      278
Aho, A.      66
Aiello, W.      243 391
Ajtai, M.      243
Algebraic criterion      157
Aligned triple      403
Aligned triple, f-linear      403
Almost one-to-one function      263
Almost-NP      389
Almost-P      318
Alon, N.      242
Alphabet      4
Alternating tree      92
Alternating Turing machine (ATM)      90 217
Alternating Turing machine (ATM), accepting computation subtree      90
Alternating Turing machine (ATM), existential configuration      90
Alternating Turing machine (ATM), existential state      90
Alternating Turing machine (ATM), polynomial-time      90
Alternating Turing machine (ATM), universal configuration      90
Alternating Turing machine (ATM), universal state      90
AM      362
AM hierarchy      365 370
AM2 circuit      241
AM2 Circuit Value      241
Amplification of accepting probability      299
AP-reduction      450
Approx-BP      74
Approx-GColor      74
Approx-KS      69
Approx-SCS      74
Approximation      see also "c-approximation" "r-Approx-
Approximation scheme, fully      69
Approximation scheme, fully probabilistic      350
Approximation scheme, polynomial-time      69
Approximation to a counting function      350
Approximation to a counting problem      350
Approximation to an optimization problem      64 68 430
Approximation to Traveling Salesman Problem (TSP)      65
Approximation to TSP      65
Approximation, ratio      65 430
Arithmetic hierarchy      79
Arora, S.      75 450 451
Arthur machine      362
Arthur — Merlin proof system      361 362
Arvind, V.      391
ASPACE(s(n))      91
ASSIGNMENT      see "Boolean assignment"
ATIME(t(n))      91
ATM      see "Alternating Turing machine"
Aut(G)      388
Automata theory      96
Automorphism      170 388
Axiomatizable theory      128
Axiomatizable theory, sound      128
Axiomatizable theory, theorem      128
Axis-parallel line      403
B      8
b-terminal      213
Babai, L.      352 390 450
Bach, E.      143
Balcazar, J.      283
Balter, T.      143
Barrington, D.      183 193
Beals, R.      242
Beame, C.      242
Beigel, R.      319
Belanger, J.      284
Bellare, M.      451
Ben-Or, M.      243 450
Bennett, C.      143 319
Berkowitz, S.J.      242
Berlekamp, E.      450
Berman — Hartmanis Isomorphism Conjecture      251
Berman — Hartmanis Isomorphism Conjecture, EXP version      263 266
Berman, L.      283 352
Berman, P.      283
Bern, M.      450
Bernstein — Schroeder — Cantor Theorem      246
Bernstein, E.      23 122
Best, M.R.      192 193
BFG      see "Boolean Formula Game"
BH      108
BHP      see "Bounded Halting Problem"
bi-immune set      263
bi-immune set, relative      282
Bin Packing (BP)      74
Binary tree      150
Bipartite graph      149
Bipartite graph property      149 158 173
Blank symbol ( $\lambda$ )      8
Blum's Speed-up Theorem      18 39
Blum, A.      76
Blum, L.      143
Blum, M.      42 450
Blum, N.      242
Bollobas, B.      193
Book, R.      42 112 143 283
Boolean assignment      6
Boolean assignment, invariant      171
Boolean assignment, partial      6
Boolean assignment, truth      6
Boolean circuit      103 195
Boolean circuit, AM2      241
Boolean circuit, depth      196
Boolean circuit, fanin      195
Boolean circuit, fanin, bottom      223
Boolean circuit, generated by a DTM      103
Boolean circuit, interpreter      203
Boolean circuit, levelable      222 343
Boolean circuit, monotone      205
Boolean circuit, planar      230
Boolean circuit, polynomial-size      199 262 304
Boolean circuit, random      234
Boolean circuit, size      196
Boolean formula      6
Boolean Formula Game (BFG)      104 105 111
Boolean formula, 3-CNF      50 87 107

1 2 3 4 5

О проекте