|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Du D.-Z., Ko K.-I. — Theory of computational complexity |
|
|
|
| Предметный указатель |
Goldreich, O. 390 391
Goldschlager, L.M. 242 243
Goldsmith, J. 284
Goldwasser, S. 390 391
Graham, R.L. 450
Graph Accessibility (GAcc) 218
Graph Coloring (GColor) 74
Graph Consistency (GC) 109
Graph Isomorphism (GIso) 117 140 381 390
Graph Nonisomorphism ( ) 355 388 390
Graph property 148
Graph property, bipartite 149
Graph property, monotone 161
Graph(s) 44 147 see
Graph(s), Boolean function representation 147
Graph(s), complement 246
Graph(s), connected 148
Graph(s), cubic 443
Graph(s), directed see "Digraph"
Graph(s), Euclidean 66
Graph(s), Eulerian 67
Graph(s), factor-critical 192
Graph(s), isomorphic 148
Graph(s), k-colored 87
Graph(s), nonplaner 188
Graph(s), planar 156
Graph(s), scorpion 189
Graph(s), simple 44
Greatest common divisor 114
Greenlaw, R. 243
GRN see "Generalized Ramsey Number"
Grollman, J. 143
Group 4
Guess-and-verify algorithm 17 44
Halldorsson, M. 434
Halting of Turing machine(s) (TM) 9 28
Halting probability, of a PTM 293
Halting problem 28 48
Halting problem, relativized 125
Hamiltonian circuit 45
Hamiltonian Circuit (HC) 45 53 67
Hamiltonian Circuit (HC), paddability 251
Hardness 47
Hartmanis, J. 42 143 283 284 352 391
Hashing function 376
Hashing function, linear 377
Hashing function, linear, random 377
Hashing function, universal 376
Hastad, J. 143 242 243 352 391 433 434 451
HC see "Hamiltonian Circuit"
Heller, H. 143 319
Hellman, M. 143
Hemachandra, L.A. 284 319 352
HEX 110
High hierarchy 351
High hierarchy, relativized 351
Holt, R.C. 192
Homer, S. 284
Hopcroft, J. 42 66 96 143
Hopf index formula 172
Hu, X.-D. 193
Huang, M.A. 319
Hunt, H.B. III 112
Ibarra, O.H. 71 75
IEE see "Integer Expression Equivalence"
Illies 193
Immerman, N. 42 242
Immune set 263
Implicant 6
Implicant prime 6
Independence results 127
Independent set 53
Independent Set (IS) 53 245 435
Inner product 278
Integer expression 109
Integer Expression Equivalence (IEE) 109
Integer Factoring (Factor) 116 122
Integer Programming (IP) 45
Interactive proof system 117 355 360 387 393
Interactive proof system, multi-prover 446
Interactive protocol 387
Interactive protocol, k-prover 446
Interactive Turing machine 360
Invariant assignment, of a symmetric permutation 171
Inverter 239
Invertible function, polynomial-time 247
Invertible reducibility, polynomial-time 247
IP 55 127 361 see
IS see "Independent Set"
is*(G) 437
IS-b 435
Iso-degree 276
Isolation Lemma 237 338
Isomorphism type 276
Isomorphism, polynomial-time 246
Jerrum, M.R. 352
Jiang, T. 112
Johnson, D. 75 76 390
Join 80 256
Joseph — Young Conjecture 267
Joseph — Young Conjecture, EXP version 267
Joseph, D. 266 283 284
K 28
K(a) 314
k-colored graph 87
k-creative set 266 281
k-truth-table reducibility, polynomial-time 256
k-UP 140
Kahn, J. 193
Kannan, S. 450
Karloff, H. 433 451
Karmarkar, N. 76 143
Karp conjecture 163
Karp, R.M. 75 76 143 193 242 243 319
Khachiyan, L. 143
Khanna, S. 76
Killian, J. 391 451
Kim, C.E. 71 75
King, V. 193
Kirkpatrick, D. 192
Kiwi, M. 451
Kleene closure 4
Kleene, S.C. 42
Kleitman, D.J. 193
Knapsack (KS) 69
Knuth, D. 115
Ko, K. 42 76 111 112 143 243 283 284 319 352 451
Koebler, J. 391
Kolmogorov complexity 42
Kolmogorov, A.N. 132
Kozen, D. 112
Kranakis, E. 143
KS see "Knapsack"
Kuratowski's theorem 188
Kurtz, S. 284
Kwiatkowski, D.J. 193
L(M) 11
L(M, A) 78
L(M, f) 60
L-reduction 435
Ladner, R. 75 143 243
Landau, S. 242
Language 4
Language class 4
Language, computable 10
Language, context-sensitive 35
Language, recursive 10
Language, recursively enumerable (r.e.) 10
Laplace expansion 47
Laplante, S. 243
| Lautemann, C. 319
Law of quadratic reciprocity 291
Lawler, E.L. 67 71 237
LE 348
Lebesgue measure 132
Lefshetz' Fixed Point Theorem 170
Legendre symbol 291
Legendre — Jacobi symbol 291
Length of a string 4
Length-increasing function 247
Levelable circuit 222 343
Levin, L. 75 450
Lewis, P.M. 42
Lexicographic ordering 4
Li, M. 42 243
Lin, C.-L. 111 112 451
Line 403 416
Linear congruence generator see "Pseudorandom generator"
Linear extension 348
Linear function 425
Linear function on an aligned triple 403
Linear function, recovering system 425
Linear programming 143
Linear speed-up theorem 20
Linearity test system 425
Link 168
Lipton, R.J. 193 242 243 450
Literal 6
Liu, C.L. 67
LOG 239 396
Log-space uniformity 216
LOGCFL 110
logspace 21
Long, T. 112 143 352
Longest Direct Circuit 109
Longest Path (LP) 449
Loop in a digraph 149
Lovasz, L. 75
Low hierarchy 351
Low hierarchy, relativized 351
Low-degree test system 411 414 416
Loxton, J.H. 143
lp see "Longest Path"
Lund, C. 76 390 391 450 451
Lupanov, O.B. 242
Lynch, N. 76 283
M 317
Mahaney, S. 283
Maier, D. 76
MAJ 342
Majority quantifier 307
Majority vote 299
MAJSAT 333
Manders, K. 112 319
Many-one reducibility 47
Many-one reducibility,  279
Many-one reducibility, log-space 218
Many-one reducibility, polynomial-time 47 74 430
Matching 67 348
MAX-CLIQUE 59 64
MAX-SNP 450
MAX-SNP-completeness 450
Maximal subset 282
Maximum satisfiability problem 430
Mayr, E.W. 243
McKenzie, P. 242
McMillan's theorem 5
MCV see "Monotone Circuit Value"
Merlin machine 363
Merlin machine, accepting probability 364
Merlin machine, configuration 363
Meyer, A. 111 283
Micali, S. 390 391
Miller, G. 319
Milner, E.C. 192
Min-Bisection 449
Min-NFA see "Minimal Nondeterministic Finite Automaton"
Min-TSP 74
Minimal Nondeterministic Finite Automaton (Min-NFA) 110
minimax 154
Minimax-3dm 109
Minimax-Circuit 109
Minimax-Clique 109
Minimum matching problem 67
Minimum spanning tree problem 66
Minterm 6 149
MIP 450
Mitchell, J. 451
Monoid 4
Monotone circuit 205
Monotone Circuit Value (MCV) 229
Moore, D. 283
Moran, S. 243 390
Motwani, R. 319
Mulmuley, K. 243 277 352
Multilinear extension 398
Multilinearity test system 399 407
Multiplication 125
Multiplication of integers 239
Multiplication of permutations 239
Myhill, J. 283
Nand Circuit Value 241
NAND gate 241
NC 217
NC reducibility 241
Neciporuk, E.I. 188
Negation 5
Negligibility 122
Network 230
Network, flow 230
NEXP 21
NEXP-complete set 107
NEXPPOLY 396
Nick's class 242
Nisan, N. 319 391
Niven, I. 114
NLOGSPACE 21 219
NLOGSPACE-complete set 219
Nonadaptive proof system 394
Nondeterministic Turing machine (NTM) 14 see
Nondeterministic Turing machine (NTM), accepting a string 15
Nondeterministic Turing machine (NTM), accepting path 15
Nondeterministic Turing machine (NTM), computation 14
Nondeterministic Turing machine (NTM), computing a function 16
Nondeterministic Turing machine (NTM), halting path 15
Nondeterministic Turing machine (NTM), k-ambiguous 140
Nondeterministic Turing machine (NTM), output 15
Nondeterministic Turing machine (NTM), unambiguous 120
Nondeterministic Turing machine (NTM), universal 25
Nonuniform complexity class 216
Nonuniform- 216
Nonuniform- 221
Nonuniform- 222
Nonuniform- 216
Nonuniform-NC 217
Normal subgroup 174
Not-All-Equal-3Sat 72
NP 21 43 410
NP-complete set 47
NP-complete set, natural 48 245 251
NP/poly 203
NPSPACE 33
NSPACE(s(n)) 19 21
NTIME(t(n)) 19
NTM see "Nondeterministic Turing machine"
Odd Maximum Flow (OMF) 230
Ogihara, M. 284
Ogiwara, M. 283
Oliver, R. 193
OMF see "Odd Maximum Flow"
|
|
|
| Реклама |
|
|
|
|
|
О проекте