|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Du D.-Z., Ko K.-I. — Theory of computational complexity |
|
|
|
| Предметный указатель |
Boolean formula, 3-DNF 87
Boolean formula, bounded variable 95
Boolean formula, clause 7
Boolean formula, conjunctive normal form 7 50 72
Boolean formula, disjunctive normal form 6 72
Boolean formula, r-unsatisfiable 394
Boolean function 5
Boolean function, elusive 153
Boolean function, graph property 148
Boolean function, monotone 148 205
Boolean function, symmetric 158
Boolean function, trivial 149
Boolean function, weakly symmetric 158
Boolean hierarchy 108
Boolean matrix multiplication 218
Boppana, R. 242 390 434
Borel field 132
Borel set 132
Borodin, A. 242 243 277
Bounded Halting Problem (BHP) 48 116
Bounded Halting Problem (BHP), relativized 84
Bounded variable, in a Boolean formula 95
bp see "Bin Packing"
BP(A) 337
BP-operator 336
bpp 298
BPP machine, universal 304
BPP Theorem 308
BPP Theorem, generalized 309
Branching program 182
Branching program,  -computation 184
Branching program, bounded-width 182
Branching program, permutation 182
Brightwell, G. 352
Broder, A.Z. 352
Buss, J. 64 76
Busy beaver 40
Busy Beaver, time-bounded version 40
C(f) 196
c-self-reducibility 257
Cai, J.-Y. 112 193 243 284 352
Cantor space 132
Cantor, G. 27
Carter, J.L. 391
CC 234
Census function 254
Certificate 44
CFL 110
Chandra, A. 111 112 242
Characteristic function 18 62
Characteristic sequence, of a set 131
Characterization of NP 43 410
Characterization of PH 82 91 451
Characterization of PSPACE 93 451
Christofides, N. 75
Church — Turing thesis 11
Church — Turing Thesis, extended 22
Circuit see "Boolean circuit"
Circuit size complexity 196 199
Circuit Value Problem (CVP) 103 229 276
class see "Complexity class" "Language
Clause 7
Clause, prime 7
CLIQUE 52 58 246
Clique indicator 207
Clique of a graph 52
Clique 205
Clocked machine see "Turing machine"
CNF see "Conjunctive normal form"
Cobham, A. 42
Coding 4
Coding theory 413
Coffman, E. 76
Collapsing degree 276
Collapsing of polynomial-time hierarchy 83
Comparator circuit value 234
Comparator gate 234
Complementary predicates 365
Completeness 47
Complexity class 18
Complexity class, nonuniform 216
Complexity class, uniform 216
Complexity core, polynomial-time 282
Complexity measure 22 see "Time
Composition of probabilistically checkable proof (PGP) systems 419 423
Computable function (language) 11
Computable function (language), feasibly 21
Computable function (language), partial 11
Computable real number see "Real number"
Computational model 11
Computational model, nondeterministic 11
Computational model, nonuniform 11
Computational model, probabilistic 11
Computational model, reasonable 11 22
Concatenation 4
Condon, A. 451
Configuration 9
Configuration game 99
Configuration game losing 99
Configuration of a Merlin machine 363
Configuration of a PTM 293
Configuration of an oracle DTM 61
Configuration, existential, of an ATM 90
Configuration, initial 9
Conjunction 5
Conjunctive normal form (CNF) 7 50 72
CONp 372
const 396
Context-free language 110
Contrastar 168
Contravariant 148
Contravariant of a boolean function 148
Convex hull 164
Cook's theorem 48 72 97 104 106 411 419
Cook, S. 48 75 216 238 242 243
Cormen, T.H. 231
coRP 300
Countable set 28
Counting problem 322
Counting problem, polynomial-time computable 323
Cramer's rule 46 47
Creative set see "p-creative set" "k-creative
Crescenzi, P. 450
Critical HC 108
Cryptography 116 119
Csansky, L. 243
Curve 417
Curve, degree-k 417
CVP see "Circuit Value Problem"
CYCLE 44 150
CYCLE COVER 328
Cycle in a graph 44 150
Cylinder 132 280
d(F) 181
d-self-reducibility 257
Daley, R. 42
De Morgan's law 196
Decision problem 58 322
Decision problem, partied 430
Decision time 419
Decision tree 150
Decision tree complexity 151
Decision tree, child node 150
Decision tree, depth 151
Decision tree, parent node 150
Decisive characterization, of BPP 308
Decisive characterization, of RP 307
Degree 276
Degree, collapsing 276
Delayed diagonalization 119
| DeMoive — Laplace Limit Theorem 225
density 254
Density, subexponential 266
Derandomization 277
det X 45
Determinant of a Polynomial Matrix (DPM) 289
Determinant, of a polynomial matrix 289
Determinant, of an integer matrix 45 238 289
Determinisitic Turing machine (DTM) see "Turing machine"
Deterministic Finite Automata Intersection 110
Deutsch, D. 122
DFA-Int see "Deterministic Finite Automata Intersection"
DGIso 140
Diagonalization 27
Diagonalization, delayed 119
Diagonalization, stage construction 135
Diffie, W. 143
Digital signature 119 140
Digraph 149
Dimension, of a face 164
Directed graph see "Digraph"
Disjunction 5
Disjunctive normal form (DNF) 6—7 72
Distance Lemma 208
Distance Lemma, second 213
Distance of two functions 399
DNF see "Disjunctive normal form"
Double encoding 420 448
DP 108
DPM see "Determinant of a Polynomial Matrix"
DSPAGE(s(n)) 18
DTIME(t(n)) 18
DTM see "Deterministic Turing machine"
Du, D.-Z. 193 283 352
Du, X. 451
Dual 148
Dual of a boolean function 148
Dunne, P.E. 242
Dynamic programming 70
EDGE 44 147
Edge of a graph 44 147
Edmonds, J. 42
Elementary collapse 166
Elementary product 6
Elementary sum 7
Elgot, C.C. 42
Elusiveness 153
Empty string 4
Encoding of a boolean circuit 216
Encoding of a Turing machine (TM) 24
Encoding, error detecting/correcting 411 416
Entry 420
Enumerable set 28
Enumeration of NP 27
Enumeration of P 26
Enumeration of PSPACE 27
Enumeration of Turing machine(s) (TM) 24
Enumeration of Turing machine(s) (TM), clocked 24
Equivalence of probabilistic Turing machine (PTM) 296
Erdoes — Rado Sunflower Lemma 210
Error detecting/correction encoding 411 416
Error probability, of a PTM 294
Euclidean graph 66
Euler characteristic 165 166
Euler function 114 124
Euler's criterion 291
Euler's theorem 114
Eulerian circuit 67
Eulerian circuit problem 67
Eulerian graph 67
Even, S. 111
Exact-Clique 58 84 108
Exact-TSP 74
Exclusive-OR 6
EXP 21 102
Exp-BHP see "Exponential-time Bounded Halting Problem"
EXP-complete set 102
Exp-CVP see "Exponential-Size Circuit Value Problem"
Exp-Sat 107
Expander 439
Exponential-Size Circuit Value Problem (Exp-CVP) 103
Exponential-time Bounded Halting Problem (Exp-BHP) 102
Exponentiation, modulo an integer 114 124
EXPSPACE-complete set 108
EXPSPAGE 21
Extended Church — Turing Thesis 22
Extracting a Bit 217
F* 149
Face 164
Face, dimension 164
Face, free 166
Face, maximal 166
Factor see "Integer Factoring"
false( ) 155
Fanin 195
Feasible subgraph 445
Feasibly computable problem 21
Feather, T. 243
Feige, U. 450 451
Fenner, S. 284
Fermat's theorem 114
FewP 350
Finite-to-one function 263
Fischer, M. 242
Fixed point 170 174
Fixed point theorem 170 174
Fixed Point Theorem, Lefshetz' 170
Flow, of a network 230
Fortnow, L. 243 352 390 391 450
Fortune, S. 242 283
FP 21 323
FPSPACE 21
Friedman, H. 42
Frieze, A.M. 143
Fuerer, M. 42
Fully polynomial-time approximation scheme 69
Fully probabilistic polynomial-time approximation scheme 350
Fully space-constructibility 27
Fully time-constructibility 26
Function see also "Boolean function"
Function, length-increasing 247
Function, partial 8 10
Function, super-polynomial 30
Function, total 10
Furst, M. 243 352
Gabber, O. 439
GAcc see "Graph Accessibility"
Gacs, P. 319
Galil, Z. 439
Galois field 174 278
Game see "Two-person game"
Gao, S.-X. 193
Garey, M.R. 75 76 450
Gate-elimination method 198
GC see "Graph Consistency"
GCD 114
GColor see "Graph Coloring"
Gemmell, P. 450
General Matching (GM) 348
Generalized BPP Theorem 309
Generalized Ramsey Number (GRN) 87
Geography 100
Geometric simplicial complex 164
GF(m) 174 278
Gill, J. 143 319
girth 175
Girth of a graph 175
GIso see "Graph Isomorphism"
GM see "General Matching"
Goldman, M. 242
|
|
|
| Реклама |
|
|
|
|
|
О проекте