Algorithms and Complexity (eBook)

Front Cover 1
Algorithms and Complexity 4
Copyright Page 5
Table of Contents 10
Preface 6
List of Contributors to Volume A 8
CHAPTER 1. Machine Models and Simulations 16
1. Introduction 18
2. Sequential machine models 31
3. The second machine class 53
4. Parallel machine models outside the second machine class 69
Acknowledgment 75
References 76
CHAPTER 2. A Catalog of Complexity Classes 82
1. Preliminaries 84
2. Presumably intractable problems 98
3. Provably intractable problems 116
4. Classes that count 121
5. Inside P 140
6. New developments, tables and figures 158
References 167
CHAPTER 3. Machine-Independent Complexity Theory 178
1. Introduction 180
2. Simple Turing machines and space complexity 180
3. Recursion, padding and compression 182
4. Gaps and arbitrary speed-up 186
5. Effective speed-up 190
6. Fundamental Theorem for STM space 192
7. Machine independence 193
Acknowledgment 200
References 200
CHAPTER 4. Kolmogorov Complexity and its Applications 202
1. Introduction 204
2. Mathematical theory 211
3. Applications of compressibility 229
4. Example of an application in mathematics: weak prime number theorems 236
5. Applications of incompressibility: proving lower bounds 237
6. Resource-bounded Kolmogorov complexity and its applications 251
7. Conclusion 262
Acknowledgment 262
References 263
CHAPTER 5. Algorithms for Finding Patterns in Strings 270
1. Introduction 272
2. Notations for patterns 273
3. Matching keywords 277
4. Matching sets of keywords 288
5. Matching regular expressions 297
6. Related problems 303
7. Concluding remarks 310
Acknowledgment 310
References 310
CHAPTER 6. Data Structures 316
1. Introduction 318
2. The dictionary problem 320
3. The weighted dictionary problem and self-organizing data structures 334
4. Persistence 338
5. The Union-Split-Find problem 339
6. Priority queues 341
7. Nearest common ancestors 343
8. Selection 344
9. Merging 346
10. Dynamization techniques 347
References 349
CHAPTER 7. Computational Geometry 358
1. Introduction 360
2. Techniques and paradigms 360
3. Convex hulls 363
4. Voronoi diagrams 367
5. Proximity problems 371
6. Linear programming 375
7. Triangulation and decomposition 379
8. Planar point location 381
9. Multidimensional trees 383
10. Range search 385
11. Visibility computations 389
12. Combinatorial geometry 391
13. Other topics 393
14. Conclusion 395
References 395
CHAPTER 8. Algorithmic Motion Planning in Robotics 406
1. Introduction 408
2. Statement of the problem 409
3. Motion planning in static and known environments 412
4. Variants of the motion planning problem 430
5. Results in computational geometry relevant to motion planning 436
Acknowledgment 440
References 440
CHAPTER 9. Average-Case Analysis of Algorithms and Data Structures 446
0. Introduction 448
1. Combinatorial enumerations 451
2. Asymptotic methods 460
3. Sorting algorithms 473
4. Recursive decompositions and algorithms on trees 488
5. Hashing and address computation techniques 507
6. Dynamic algorithms 526
Acknowledgment 535
References 535
CHAPTER 10. Graph Algorithms 540
Prelude 542
1. Representation of graphs 542
2. Basic structure algorithms 566
3. Combinatorial optimization on graphs 594
References 627
CHAPTER 11. Algebraic Complexity Theory 648
1. Introduction 650
2. Addition chains 652
3. Computation sequences 652
4. Substitution 653
5. Degree of transcendency 655
6. Geometric degree 656
7. Derivatives 659
8. Branching 660
9. Complexity classes 663
10. Matrix multiplication and bilinear complexity 665
11. Degeneration and asymptotic spectrum 668
12. Lower bounds for rank and border rank 671
13. Fourier transform 675
14. Complete problems 676
15. Conclusion 679
References 679
CHAPTER 12. Algorithms in Number Theory 688
1. Introduction 690
2. Preliminaries 692
3. Algorithms for finite abelian groups 700
4. Factoring integers 712
5. Primality testing 721
Acknowledgment 727
References 727
CHAPTER 13. Cryptography 732
1. Introduction 734
2. Basics 734
3. The goals and tools of cryptology 737
4. Mathematical preliminaries 738
5. Complexity-theoretic foundations of cryptography 740
6. Privacy 743
7. Generating random or pseudo-random sequences and functions 750
8. Digital signatures 754
9. Two-party protocols 757
10. Multi-party protocols 761
11. Cryptography and complexity theory 763
Acknowledgment 764
References 765
CHAPTER 14. The Complexity of Finite Functions 772
1. Introduction 774
2. General circuits 775
3. Bounded-depth circuits 780
4. Monotone circuits 795
5. Formulas 801
6. Branching programs 811
7. Conclusion 814
Acknowledgment 815
References 815
CHAPTER 15. Communication Networks 820
1. Introduction 822
2. Communication problems 824
3. The Ajtai, Komlós and Szemerédi Theorem 835
Acknowledgment 846
References 846
CHAPTER 16. VLSI Theory 850
1. Introduction 852
2. VLSI complexity measures 854
3. The VLSI model 857
4. The basic lower bound argument 859
5. A geometric separator theorem 860
6. The communication complexity of Boolean predicates 861
7. The communication complexity of Boolean functions with many outputs 868
8. A lower bound on the switching energy of VLSI chips 872
9. Upper bounds on the AT2 -complexity of VLSI chips 877
Acknowledgment 880
References 880
CHAPTER 17. Parallel Algorithmsfor Shared-Memory Machines 884
1. Introduction 886
2. Efficient PRAM algorithms 888
3. Models of parallel computation 909
4. NC-algorithms and P-complete problems 921
5. Conclusion 946
Acknowledgment 947
References 947
CHAPTER 18. General Purpose Parallel Architectures 958
1. Introduction 960
2. Some networks 961
3. Routing 965
4. Universality 974
Acknowledgment 983
References 984
Subject Index 988