|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Leeuwen J.V. — Handbook of Theoretical Computer Science: Algorithms and Complexity |
|
|
|
| Предметный указатель |
Boolean function, multi-output 785
Boolean function, single-output 785
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 237 245
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 881 894 919
Brent’s scheduling principle 874—875
Brownawell’s bound 657
Bubble sort 467
Bucket algorithm 493 514
Bucket occupancy, maximum 499 517
Bucket sort 892 894
Buffer (in a routing algorithm) 958
Bulk synchrony 968
Butterfly network 863 947
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 913—915 919
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 897—901
Circuit complexity 36 760
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 130
CIRCUIT VALUE problem, bounded width 130
CIRCUIT VALUE problem, comparator 132
CIRCUIT VALUE problem, monotone 137 926—929
CIRCUIT VALUE problem, planar 137
Circuit, approximator 781
Circuit, arithmetic 635 905 913 916
Circuit, boolean 36 760
Circuit, bounded-depth 765
Circuit, depth of a 36
Circuit, induced 767
Circuit, monotone 36 773 780
Circuit, probabilistic 773
Circuit, size of a 36
Circuit, unbounded fan-in 36 898—900 903—905 908 912
Circuit, uniform family of 872 898 900 902—903
Circulation 591
Circulation theorem 591
Class group 681 692 697 702
Class group composition algorithm 682
Class group method 697
Class group reduction algorithm 681 710
Class group, prime form 683 682
Class number 682 697 711
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 921
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 436
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 891 931
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 926
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 709
Complex multiplication test 709
| complexity 638
Complexity class 11 182 648 761 796
Complexity class, nonuniform 75 116
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 182
Complexity, monotone circuit 780
Complexity, multiplicative 640
Complexity, nonscalar 638
Complexity, of a matrix 660
Complexity, self-delimiting 202 209—211
Component 529
Component, connected 529 882 894
Component, strong 919
Component, strongly connected 571
Component, weak 571
Composite number 88 90 114—115
Compositeness test 706
Composition of quadratic forms see class group composition Algorithm
Compressible in time T 243
Compressible string 214 242—246
Compression theorem 167
Compression, language 242—246
Compression, optimal 243
Computable function 193 197 207
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 635
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 393
Computer, general-purpose 945 959
Conditional Kolmogorov complexity 198
Configuration 7 808
Configuration space 396
Configuration space, connected components of 396
Configuration space, cross sections of 403 414
Configuration space, geometric complexity of 398
Configuration space, single component of 399 411
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 882 894
Connected component,  529
Connected component, (in algebraic complexity theory) 647
Connected component, bi 529 553
Connected component, tri 530 553
Connection problem 809
Connection problem, generalized 812
Connectivity 403 552
Connectivity function 787
Connectivity graph 396 402
Connectivity, edge 554
Connectivity, four 882 886
Connectivity, tri 882 885—886
Connectivity, two-edge 885
Connectivity, vertex 552
Connector 809
Connector, generalized 812
Constraint curve 398
Constructible space bound 168
Context-free language 137 233 235 650 921—922
Context-sensitive language 100—101 233 235
Continued fraction 512 639
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 2
Cook’s theorem 85
Coordinate recurrence method 684 692 693 700 703 705
Counting 436
Counting argument 235 763
Counting problem 71
Counting Turing machine (CTM) 74 106
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 414
Criticality problem 93
Crossing number 528
Crossing sequence 223 232 848 854
Cryptanalysis 720
Cryptographic compiler 748
Cryptographic operator 723
Cryptographic protocol 723
Cryptography 111—112 236 719 720
Cryptology 675 720
Cryptosystem, knapsack-based 730
Cryptosystem, probabilistic public-key 730
Cryptosystem, public-key 729
Cryptosystem, secret-key 719
CTM see counting Turing machine
Cube, binary n-dimensional 947
|
|
|
| Реклама |
|
|
|
|
|
О проекте