|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Leeuwen J. (ed.), Meyer A.R., Nivat M. — Algorithms and Complexity, Volume A |
|
|
|
| Предметный указатель |
Boolean direct product 786
Boolean formula 143
Boolean function, monotone 780 (see also Basis of)
Boolean function, multi-output 785 (see also Basis of)
Boolean function, single-output 785(see also Basis of)
Boolean function, slice 780
Boolean hierarchy 93
Boolean matrix multiplication 786
Boolean matrix rank 225
Boolean predicate 846
Boolean sorting 786
Boolean sum 786
Border rank 651
Bound, Alder — Strassen 657
Bound, Brownawell’s 636
Bounded Tiling 56
Bounded-depth circuit 765
Box decomposition 357
Boyer — Moore algorithm 267
bpp 120
Branch point (of a computation tree) 113
Branching complexity 646
Branching instruction 645
Branching program 796
Branching program, deterministic 796
Branching program, nondeterministic 796
Branching program, permuting 798
Breadth-first search (BFS) 539
Brent’s scheduling principle 874—875
Brownawell’s bound 657
Bubble sort 467
Bucket algorithm 493
Bucket occupancy, maximum 499
Bucket sort 892
Buffer (in a routing algorithm) 958
Bulk synchrony 968
Butterfly network 863
Butterfly network, directed 952
Capacity measure 20
CC 132
CCV-equivalent problem 132—133
Cell decomposition 401
Cell decomposition, adjacency in 402
Cell decomposition, Collins’ 401
Cell decomposition, sign-invariant 401
Cell decomposition, topology of 402
Center 32
Certificate 740
Certified mail 744
CFL 234
Channel 7
Characteristic function 456
Characteristic polynomial 650
Characteristic predicate 855
Characteristic sequence 207
Chebychev polynomial 643
Chebychev’s Inequality 212
Checksum 725
Chinese postman problem 566
Chinese remainder theorem 653
Chinese Remainder Theorem method 689
Chip 842
Chomsky hierarchy 233
Church’s thesis 4
Ciphertext 719
Circle, largest empty 359
Circle, smallest enclosing 363
Circuit 842 (see
Circuit complexity 36
Circuit complexity, monotone 780
Circuit design problem 837
Circuit family 766
Circuit family, nonuniform 75
Circuit family, uniform 766
Circuit switching 808
Circuit switching network 808
Circuit value problem 126
CIRCUIT VALUE problem, bounded width 130
CIRCUIT VALUE problem, comparator 132
CIRCUIT VALUE problem, monotone 137
CIRCUIT VALUE problem, planar 137
Circuit, approximator 781
Circuit, arithmetic 635
Circuit, boolean 36
Circuit, bounded-depth 765
Circuit, depth of a 36
Circuit, induced 767
Circuit, monotone 36
Circuit, probabilistic 773
Circuit, size of a 36
Circuit, unbounded fan-in 36 912
Circuit, uniform family of 872
Circulation 591
Circulation theorem 591
Class group 681
Class group composition algorithm 682
Class group method 697
Class group reduction algorithm 681
Class group, prime form 683
Class number 682
Classification, de Groote — Heintz 657
Classifier 817
Classifier, approximate 821
Claw-free function 726
Cleartext see Plaintext
CLIQUE 83
Clique function 780
Clique indicator 781
Closest pair 357
Clustering Problem 359
co — NP 89—90
Co — NP-complete 92
Coalesced hashing 504
Code, straight-line 915—917
Cograph 546
Coin-flipping, -over-the-telephone 744
Coin-tossing, deterministic 878
Collective 192
Collins cell 402
Collision avoidance 393
Collision constraint 396
Collision detection 422
Collision-free path 393
Combinatorial enumeration 434
Combinatorial geometry 376
Combinatorial optimization 579
Combinatorial structure, labeled 441
Combining lemma 555
Commentz — Walter algorithm 278
Communication complexity 788
Communication complexity, deterministic two-way 847
Communication complexity, Las Vegas 848
Communication complexity, nondeterministic 847
Communication network 807
Communication time 838
Comparator 811
Comparator circuit value 931
Comparator network 887—888
Comparison-based data structure 305
Compatible reduction 79
Complementary language 71
Complete, co-NP- 92
Complete, NP- 15 84
Complete, NP- in the strong sense 86
Complete, P- 906—907
Complete, PSPACE- 15
Completeness (for a class) 83 (see also Complete)
Completeness (for a class), PR- 246—247
Complex analysis 447
Complex division 658
| Complex inversion 658
Complex multiplication field 679
Complex multiplication test 709
complexity 638
Complexity class 11
Complexity class, nonuniform 75
Complexity class, space 796
Complexity class, time 761
Complexity classes, catalog of 67
Complexity hierarchy 167 (see also Compression theorem)
Complexity measure 433
Complexity measure, Blum 180
Complexity of games 41
Complexity oscillations 206
Complexity sequence 177 (see also Prospective or realizable space complexity)
Complexity theory 3
Complexity theory, algebraic 633
Complexity theory, machine-independent 163
Complexity, abstract 180
Complexity, additive 640
Complexity, algebraic 399
Complexity, arithmetic 650
Complexity, asymptotic 652
Complexity, bilinear 650
Complexity, branching 646
Complexity, circuit 36 760
Complexity, machine-based 181
Complexity, monotone circuit 780
Complexity, multiplicative 640
Complexity, nonscalar 638
Complexity, of a matrix 660
Complexity, self-delimiting 202
Component 529
Component, connected 529
Component, strong 919
Component, strongly connected 571
Component, weak 571
Composite number 88 90
Compositeness test 706
Composition of quadratic forms see Class group composition algorithm
Compressible in time  243
Compressible string 214
Compression theorem 167
Compression, language 242—246
Compression, optimal 243
Computable function 193 (see
Computable function, effectively 193
Computable number 223(see also Recursive real)
Computable operator 172
Computable probability 213
Computable, effectively 3
Computation 8
Computation sequence 635
Computation tree 73
Computation tree, accepting 43
Computation tree, cost function of 646
Computation tree, cost of 646
Computation, accepting 8
Computation, algebraic 635
Computation, asynchronous 9
Computation, divergent 8
Computation, full 8
Computation, generic 648
Computation, off-line 7
Computation, on-line 7
Computation, recognizing 8
Computation, synchronous 9
Computation, terminating 8
Computational complexity 165
Computational complexity theory, invariance of 3
Computational geometry 345
Computer, general-purpose 945
Conditional Kolmogorov complexity 198
Configuration 7
Configuration space 396
Configuration space, connected components of 396
Configuration space, cross sections of 403
Configuration space, geometric complexity of 398
Configuration space, single component of 399
Configuration, accepting 8
Configuration, final 8
Configuration, initial 8
Configuration, reachable 8
Configuration, rejecting 8
Conjecture, additivity 651
Conjecture, Harrison — Ibarra 229
Conjecture, Ostrowski’s 637
Conjecture, Rosenberg 229
Connected component 529
Connected component,  529
Connected component, (in algebraic complexity theory) 647
Connected component, bi- 529
Connected component, tri- 530
Connection problem 809
Connection problem, generalized 812
Connectivity 403
Connectivity function 787
Connectivity graph 396
Connectivity, edge 554
Connectivity, four 882
Connectivity, tri- 882
Connectivity, two-edge 885
Connectivity, vertex 552
Connector 809
Connector, generalized 812
Constraint curve 398
Constructible space bound 168
Context-free language 137
Context-sensitive language 100—101
Continued fraction 512
Continued fraction algorithm 701
Continued fraction, evaluation of 639
Continued fraction, expansion into 646
Contract-signing 744
Contraction 547
Contraction, elementary 547
Control 393
Convergence, recursive 206
Convex distance function 409
Convex hull 348
Convex layers 351
Cook’s 2DPDA theorem 272
Cook’s theorem 85
Coordinate recurrence method 684
Counting 436
Counting argument 235
Counting problem 71
Counting Turing machine (CTM) 74
Cover, edge 581
Cover, node 581
Covering 364
Covering (of a graph) 572
Covering, edge 581
CPRAM 960
CRCW PRAM 134
CREW PRAM 134
Critical orientations 407
Critical values 403
Criticality problem 93
Crossing number 528
Crossing sequence 223
Cryptanalysis 720
Cryptographic compiler 748
Cryptographic operator 723
Cryptographic protocol 723
Cryptography 111—112
Cryptology 675
Cryptosystem, knapsack-based 730
Cryptosystem, probabilistic public-key 730
Cryptosystem, public-key 729
|
|
|
| Реклама |
|
|
|
|
|
О проекте