|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Du D.-Z., Ko K.-I. — Theory of computational complexity |
|
|
|
| Предметный указатель |
One-one reducibility, polynomial-time 247 see
One-sided error 300
One-way function 119 140 269
One-way function, characterization 121
One-way function, k-to-one 122
One-way function, length-increasing 269
One-way function, strong 122
One-way function, trapdoor 124
One-way function, weak 120 266
Optimization problem 60 64 434
Optimization problem, NP-hard 430
Optimization problem, solution 64
Optimization problem, value of a solution 64
Oracle 58 397
Oracle Boolean formula 397
Oracle class 132
Oracle function 60
Oracle nondeterministic Turing machine 77 see
Oracle nondeterministic Turing machine, answer state 77
Oracle nondeterministic Turing machine, polynomial-time 78
Oracle nondeterministic Turing machine, query state 77
Oracle nondeterministic Turing machine, query tape 77
Oracle probabilistic Turing machine 310 see
Oracle probabilistic Turing machine, nonadaptive 395
Oracle Turing machine 60 61
Oracle Turing machine, answer state 60
Oracle Turing machine, computation 72
Oracle Turing machine, function oracle 60
Oracle Turing machine, polynomial-time 62
Oracle Turing machine, positive 73
Oracle Turing machine, query state 60
Oracle Turing machine, query string 61
Oracle Turing machine, query tape 60
Oracle Turing machine, robust 75
Oracle Turing machine, set oracle 61
Oracle, random 131 310 345 348
Oracle, set 61
Oracle-Sat 111 398
Orbit 172 174
Orbit of an automorphism 172
Orbit, center of gravity 172
Orponen, P. 76 283
P 21
P-bi-immune set 263
P-complete set 102 229
p-creative set, for NP 281
p-creative set, for P 280
P-immune set 263
p-isomorphic sets 246
p-selective set 281
P/log 239
P/poly 202 304
Paddable set 249
Paddable set, length-increasingly 249
Paddable set, weakly 267
Padding function 249
Pairing function 5 36
Panconesi, A. 450
Papadimitriou, C.H. 112 352 450
Parallel computation 217
Parallel random access machine (PRAM) 217
Parity 217
Parity function 151 217 222
Parity machine 334
Parity operator 334
Parity-CVP 276
Partial assignment 6
Partial computable function 10
Partial decision problem 430
Partial ordering 256
Partial ordering, polynomially related 256
Partial recursive function 10
Partied function 8 10
Partition 57 58
Partition paddability 252
Paterson, M. 283
Path 44 148
Path in a graph 44 148
Path, simple 44
Paul, W.J. 42
PCP 395
PCP(F, G) 396
PCP(r(n), q(n)) 395
PCV see "Planar Circuit Value"
Perfect Matching (PM) 236
Perm 327 357
perm(A) 327
Permanent, of a Boolean matrix 332
Permanent, of an integer matrix 327
Permutation branching program 182
Permutation group 158
Permutation group, transitive subgroup 158
Permutation, cyclic 159 184
Permutation, symmetric 171
Ph 79
Pippenger, N. 242 243
Planar circuit 230 238
Planar Circuit Value (PCV) 230
Plassmann, P. 450
Plucking operation 209
Plumstead, J. 143
PM see "Perfect Matching"
POLY 202 396
PolyLog 410
Polynomial code 413
Polynomial extension 413
Polynomial recovering system 416 418
Polynomial-size circuit 199 262 304
Polynomial-time approximation scheme see "Approximation scheme"
Polynomial-time hierarchy 79 340 354
Polynomial-time hierarchy, relativized 108 346
Polynomial-time invertible function 247
Polynomial-time invertible reducibility 247
Polynomial-time isomorphism 246
Polynomially honest function 71
Positive relativization 129
Post's Problem 119
PP 296 323
PP-completeness 333
PRAM see "Parallel random access machine"
Pratt, V. 143 242
Prefix set 71
Primality Testing (Prime) 113 115 116 291
Prime see "Primality Testing"
PrimeSat 349
Private-key cryptosystem 123
Probabilistic algorithm 117
Probabilistic interactive proof system see "Interactive proof system"
Probabilistic nondeterministic Turing machine 363
Probabilistic quantifier 307
Probabilistic Turing machine (PTM) 292 293 316
Probabilistic Turing machine (PTM), accepting an input 294
Probabilistic Turing machine (PTM), accepting probability 293
Probabilistic Turing machine (PTM), configuration 293
Probabilistic Turing machine (PTM), halting probability 293
Probabilistic Turing machine (PTM), random state 395
Probabilistic Turing machine (PTM), rejecting probability 293
Probabilistically checkable proof (PGP) systems 395
Probabilistically checkable proof (PGP) systems, checking assignments in split form 420
Probabilistically checkable proof (PGP) systems, reading a constant number of entries 420
Program of a Turing machine (TM) 8
Program over a monoid 182
Projection, of a Boolean circuit 209 213
Proof, in a PCP system 397
Pseudo polynomial-time algorithm 69
Pseudorandom generator 119 140 318
Pseudorandom generator,  -generator 318
Pseudorandom generator, linear congruence generator 140
Pseudorandom generator, quadratic residue generator 141
Pseudorandom generator, strongly unpredictable 318
| PSPACE 21
PSPACE-complete set 95
PTM see "Probabilistic Turing machine"
Public-key cryptosystem 119 123
Public-key cryptosystem, ciphertext 123
Public-key cryptosystem, decryption algorithm 123
Public-key cryptosystem, decryption key 123
Public-key cryptosystem, encryption algorithm 123
Public-key cryptosystem, encryption key 123
Public-key cryptosystem, plaintext 123
Public-key cryptosystem, Rivest — Shamir — Adleman (RSA) 124
QBF see "Quntified Boolean Formula"
qc(T) 91
QNR see "Quadratic Nonresidues"
qr see "Quadratic Residuosity"
Quadratic nonresidues 356
Quadratic residue 116 291
Quadratic residue generator see "Pseudorandom generator"
Quadratic Residuosity (QR) 116 381
Quantified boolean formula 95
Quantified Boolean Formula (QBF) 95
Quantified Boolean Formula (QBF), self-reducibility 257
Quantified Boolean formula, 3-CNF 96
Quantified Boolean formula, normal form 95
Quantifier 95
Quantifier changes, of an ATM 91
Quantifier, scope 95
Quantum Turing machine 23 122
Query bits 393
Quicksort, deterministic algorithm 287
Quicksort, randomized algorithm 288
r(f) 176
r-Approx- 65 430
r-Approx-3Sat 430
r-Approx-Clique 433
r-Approx-TSP 65
r-degree 276
r-Noclique 433
r-Unsat 431
r.e. see "Recursively enumerable language"
Rabin, M. 117 125 143 319
Rackoff, C. 143 319 390 391
Raghavan, P. 319
RAM see "Random access machine"
Random access machine (RAM) 37
Random access machine (RAM), complexity measure 38
Random bit(s) 393
Random bit(s), generator 292
Random bit(s), shared 141
Random circuit 234
Random oracle 131 310 345 348
Random restriction 223
Randomization 277
Randomized algorithm 287
Randomized decision tree 176
Randomized decision tree complexity 176
Randomized decision tree, expected depth 176
Randomized decision tree, expected time 176
Randomized reduction 337
Rank, of a matrix 277
Ravikumar, B. 112
Raz, R. 451
Razborov, A.A. 242
Real number, computable 41
Real number, computable, binary 41
Real number, computable, Cauchy 41
Real number, computable, Dedekind 41
Real number, computable, Turing 41
Real number, polynomial-time computable, binary 41
Real number, polynomial-time computable, Cauchy 41
Real number, polynomial-time computable, Dedekind 41
Recursion theory 11
Recursive function (language) 11
Recursive function (language), partial 11
Recursive function theory 11
Recursively enumerable (r.e.) language 10
Reducibility 47 see "One-one "Strong "Truth-table "Turing
Reducibility, adaptive 73
Reducibility, closed under 47
Reducibility, conjunctive see "Truth-table reducibility"
Reducibility, disjunctive see "Truth-table reducibility"
Reducibility, NC 241
Reducibility, polynomial-time invertible 247
Regular expression 96
Regular expression, extended 107
Reingold, E.M. 192
Reingold, N. 319
Relativization 78 125
Relativization, positive 129
Restriction 6 223
Restriction of a boolean function 6
Restriction of a boolean function, random 6
Restriction, random 223
Rice, H. 42
Rivest — Shamir — Adleman cryptosystem (RSA) 124
Rivest, R. 143 192
RNC 236
Rogers, H., Jr. 11 42 75 79 111
Rogers, J. 284
Roman, S. 42 450
Root, of a decision tree 150
Rosenberg, A.L. 192
RP 300
RSA cryptosystem 124
RTIME(t(n)) 296
Rubinfeld, R. 450
Running time see "Time complexity"
Russo, D. 283
Ruzzo, W. 76 112 319
Safra, S. 450 451
Saks, M. 319
SAT see "Satisfiability"
sat*(F) 430
SAT-UNSAT 108
Satisfiability (Sat) 44 249
Satisfiability (Sat), paddability 250
Satisfiability (Sat), self-reducibility 255
Savitch's theorem 32 92 382
Savitch, W. 42
SBHP see "Space Bounded Halting Problem"
sc see "Set Cover"
Schaefer, T.J. 75 111
Schoening, U. 76 143 283 352 391
Schwartz, J. 319
Scorpion graph 189
SCS see "Shortest Common Superstring"
Search problems 59 322
Seiferas, J.I. 42
Self-reducibility 255
Self-reducing tree 255
Selman, A. 143 283
Set Cover (SC) 444
Set Splitting 72
Shallit, J. 143
Shamir, A. 391
Shannon, C.E. 242
Shepherdson, J.C. 42
Sheu, M. 352
Shor, P.W. 23 122
Shortest Common Superstring (SCS) 74
Shortest Interconnection Design (SID) 445
SID see "Shortest Interconnection Design"
SIMDAG machine 217
Simon, J. 283 319 352
Simple set 263
Simple strategy 155
simplex 164
Simplex, face 164
Simplicial complex 164
Simplicial complex, abstract 164
|
|
|
| Реклама |
|
|
|
|
|
О проекте