|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Du D.-Z., Ko K.-I. — Theory of computational complexity |
|
|
|
| Предметный указатель |
Simplicial complex, collapsible 167
Simplicial complex, contractible 170
Simplicial complex, Euler characteristic 165
Simplicial complex, geometric 164
Simplicial complex, geometric representation 164
Simplicial mapping 170
Simulation 12 16 23 31
Sinclair, A. 352
Sipser, M. 319 352 391
Sivakumar, D. 284
Slice function 239
Smolensky, R. 243
SMT see "Steiner Minimum Trees"
SMT-DG see "SMT-in-Digraph"
SMT-G see "Steiner Minimum Trees-in-Graph"
SMT-in-Digraph (SMT-DG) 448
Soare, R.I. 42
Solovay, R. 319
Space Bounded Halting Problem (SBHP) 95 116
Space complexity 18 63 91 298 317
Space hierarchy theorem 28
Space-constructibility, fully 27
Spanning tree 66
Sparse set 40 202 254 265
Spielman, D. 319
sqrt see "Square Root Modulo an Integer"
Square Root Modulo a Prime 302
Square Root Modulo an Integer (SQRT) 116 122
SS see "Subset Sum"
Stage construction diagonalization 135
Stearns, R.E. 42
Steiner Minimum Trees (SMT) 448
Steiner Minimum Trees-in-Graph (SMT-G) 448
Stockmeyer, L. 111 112 352
Storer, J. 76
Straight-line arithmetic program 349
Strassen, V. 319
Straubing, H. 193
String 3
String matching 315
String, empty 4
Strong equivalence of probabilistic Turing machine (PTM) 296
Strong NP reducibility 108 140
Strongly bi-immune set 263
Strongly bi-immune set, sparse 265
Strongly unpredictable pseudorandom generator 318
Strongly unpredictable set 122
Sturgis, H.E. 42
Subexponential density 266
Subgraph Isomorphism 72
Subramanian, A. 243
Subset Sum (SS) 56 69
Sudan, M. 450
Sudborough, J.H. 112
Sum check system 401 408
Sunflower 209
Sunflower, center 209
Sunflower, petal 209
Swapping lemma 307
Swapping Lemma, second 317
Switching Lemma 223
Symmetric permutation, of a Boolean function 171
Szegedy, M. 450
Szelepcsenyi, R. 42
T-self-reducibility 280
Tally set 40 260 305
Tape compression theorem 19
Tardos, E. 242
Tarjan, R.E. 111 243
Tensor-product 426
Tensor-product test system 426
TERE see "Totality of Extended Regular Expressions"
Terminal 207 see
tetrahedron 164
Threshold function 198
Time complexity 18 19 62 78 90 295
Time complexity measure 22 38
Time complexity measure, logarithmic 38
Time complexity measure, reasonable 22
Time complexity measure, uniform 22 38
Time complexity, expected 295
Time complexity, uniform 296
Time hierarchy theorem 30
Time-constructibility, fully 26
TM see "Turing machine"
Toda, S. 352
Topological criterion 167
Totality of Extended Regular Expressions (TERE) 108
Totality of Regular Expressions (TRE) 96
Transitive closure 110
Trapdoor one-way function 124
Traveling salesman problem (TSP) 65
Traveling Salesman Problem (TSP) with triangle inequality 66 449
TRE see "Totality of Regular Expressions"
TREE 150
Tree function 154
Tree, binary 150
Tree, internal vertex 150
Tree, leaf 150
Tree, pruning 259 261
| Tree, root 150
Tree, rooted 150
triangle 164
Triangle inequality 66
Triesch, E. 193
Triple see "Aligned triple"
True( ) 155
Truth assignment 6
Truth-table 6
Truth-table reducibility, polynomial-time 73 256 see
Truth-table reducibility, polynomial-time, bounded 109
Truth-table reducibility, polynomial-time, conjunctive 256
Truth-table reducibility, polynomial-time, disjunctive 256
TSP see "Traveling Salesman Problem"
tt-condition 256
tt-self-reducibility 256
Turing machine(s) (TM) 7
Turing machine(s) (TM), clocked 26
Turing machine(s) (TM), computation 9
Turing machine(s) (TM), configuration 9
Turing machine(s) (TM), deterministic (DTM) 7
Turing machine(s) (TM), interactive 360
Turing machine(s) (TM), multi-tape 12 37
Turing machine(s) (TM), next configuration function 9
Turing machine(s) (TM), polynomial-time 21
Turing machine(s) (TM), quantum 23 122
Turing machine(s) (TM), space complexity see "Space complexity"
Turing machine(s) (TM), time complexity see "Time complexity"
Turing machine(s) (TM), universal 24
Turing reducibility 58 61—62
Turing reducibility, log-space 73
Turing reducibility, polynomial-space 64 73
Turing reducibility, polynomial-time 58 62 323
Turing reducibility, positive, polynomial-time 73
Turing, A. 42
Two-person game 99 353
Two-person game, configuration 99
Two-person game, polynomially bounded 99
Two-person game, winning strategy 99
Two-sided errors 300
Tzeng, W.-G. 112
Ullman, J. 42 66 96
Uniform complexity class 216
Uniformity, log-space 216
Universal BPP machine 304
Universal hashing function 376
Unrelativizable proof technique 127
Unsat see "r-Unsat"
UP 120 see
Valiant, L. 143 351 352
van Emde Boas, P. 242
van Melkebeek, D. 284
Vazirani, U.V. 23 122
Vazirani, V.V. 352
VC see "Vertex Cover"
vc*(G) 436
VC-b 435
VC-CG see "VC-in-Cubic-Graphs"
VC-in-Cubic-Graphs (VC-CG) 443
Vector space 278
Vertex 44 147
Vertex cover 51
Vertex Cover (VC) 51 246
Vertex Cover (VC), paddability 251
Vertex cover of a graph 51
Vertex of a graph 44 147
Vertex, adjacent 148
Vitanyi, P. 42 243
Vollmer, H. 143
Vuillemin, S. 192
Wagner, K. 143
Wang, J. 283 284
Watanabe, O. 283
Weakly paddable set 267
Wechsung, G. 319
Wegener, I. 242
Wegman, M.N. 391
Well-formed formula 128
Welsh, D.J.A. 192
Wigderson, A. 319 391
Wilson, C. 76
Winkler, P. 352
Winning strategy 99
Witness 17 44 322
Wolfe, D. 112
Wrathall, C. 111 112
Wreath product 175
Wu, W. 193
Wyllie, J. 242
Yannakakis, M. 76 112 450 451
Yao, A. 193 242 243 319 352
Young, P. 266 283
Zachos, S. 319 352
Zero-knowledge proof system 389
Zero-knowledge proof system, perfect 390
Zero-one law 132
Zhou, S. 319
ZPP 300
Zuckerman, H.S. 114 391
Zwick, U. 433 451
|
|
|
| Реклама |
|
|
|
|
|
О проекте