Foundations of Computing

frontcover......Page 1
Contents......Page 6
Preface......Page 14
1 Fundamentals ......Page 18
1.1 Examples ......Page 19
1.2.1 Substitution Method ......Page 25
1.2.2 Iteration Method ......Page 26
1.2.3 Reduction to Algebraic Equations ......Page 27
1.3.1 Ceiling and Floor Functions ......Page 31
1.3.2 Logarithms ......Page 33
1.3.3 Binomial Functions - Coefficients ......Page 34
1.4.1 Generating Functions ......Page 36
1.4.2 Solution of Recurrences ......Page 39
1.5 Asymptotics ......Page 45
1.5.1 An Asymptotic Hierarchy ......Page 46
1.5.2 Order, big-oh and small-oh -notations ......Page 48
1.5.3 Relations between Asymptotic Notations ......Page 51
1.5.4 Manipulations with 0-notation ......Page 53
1.5.5 Asymptotic Notation - Summary ......Page 54
1.6.1 Bootstrapping ......Page 55
1.6.2 Analysis of Divide-and-conquer Algorithms ......Page 56
1.7 Primes and Congruences ......Page 57
1.7.1 Euclid\'s Algorithm ......Page 58
1.7.2 Primes ......Page 60
1.7.3 Congruence Arithmetic ......Page 61
1.8 Discrete Square Roots and Logarithms ......Page 64
1.8.1 Discrete Square Roots ......Page 65
1.9.1 Discrete Probability ......Page 70
1.9.2 Bounds on Tails of Binomial Distributions ......Page 76
1.9.3 Randomness and Pseudo-random Generators ......Page 77
1.9.4 Probabilistic Recurrences ......Page 79
1.10.1 Tasks of Complexity Analysis ......Page 81
1.10.2 Methods of Complexity Analysis ......Page 83
1.10.3 Efficiency and Feasibility ......Page 84
1.10.4 Complexity Classes and Complete Problems ......Page 85
1.10.5 Pitfalls ......Page 86
1.11 Exercises ......Page 87
1.12 Historical and Bibliographical References ......Page 92
2 Foundations ......Page 94
2.1.1 Basic Concepts ......Page 95
2.1.2 Representation of Objects by Words and Sets by Languages ......Page 97
2.1.3 Specifications of Sets - Generators, Recognizers and Acceptors ......Page 100
2.1.4 Decision and Search Problems ......Page 104
2.1.5 Data Structures and Data Types ......Page 106
2.2.1 Basic Concepts ......Page 108
2.2.2 Representations of Relations ......Page 110
2.2.3 Transitive and Reflexive Closure ......Page 111
2.2.4 Posets ......Page 113
2.3 Functions ......Page 114
2.3.1 Basic Concepts ......Page 115
2.3.2 Boolean Functions ......Page 119
2.3.3 One-way Functions ......Page 124
2.3.4 Hash Functions ......Page 125
2.4.1 Basic Concepts ......Page 130
2.4.2 Graph Representations and Graph Algorithms ......Page 135
2.4.3 Matchings and Colourings ......Page 136
2.4.4 Graph Traversals ......Page 139
2.4.5 Trees ......Page 143
2.5.1 Basic Concepts ......Page 144
2.5.3 Interpretations of Words and Languages ......Page 148
2.5.4 Space of omega-languages ......Page 154
2.6.2 Semigroups and Monoids ......Page 155
2.6.3 Groups ......Page 156
2.6.4 Quasi-rings, Rings and Fields ......Page 159
2.6.5 Boolean and Kleene Algebras ......Page 160
2.7 Exercises ......Page 162
2.8 Historical and Bibliographical References ......Page 168
3 Automata ......Page 170
3.1 Finite State Devices ......Page 171
3.2 Finite Automata ......Page 174
3.2.1 Basic Concepts ......Page 175
3.2.2 Nondeterministic versus Deterministic Finite Automata ......Page 178
3.2.3 Minimization of Deterministic Finite Automata ......Page 181
3.2.4 Decision Problems ......Page 183
3.2.5 String Matching with Finite Automata ......Page 184
3.3.1 Closure Properties ......Page 186
3.3.2 Regular Expressions ......Page 188
3.3.3 Decision Problems ......Page 191
3.3.4 Other Characterizations of Regular Languages ......Page 193
3.4 Finite Transducers ......Page 195
3.4.1 Mealy and Moore Machines ......Page 196
3.4.2 Finite State Transducers ......Page 197
3.5.1 Basic Concepts ......Page 199
3.5.2 Functions Computed by WFA ......Page 204
3.5.3 Image Generation and Transformation by WFA and WFT ......Page 205
3.5.4 Image Compression ......Page 207
3.6.1 Buchi and Muller Automata ......Page 208
3.6.2 Finite State Control of Reactive Systems ......Page 210
3.7 Limitations of Finite State Machines ......Page 212
3.8.1 Transition Systems ......Page 213
3.8.2 Probabilistic Finite Automata ......Page 214
3.8.3 Two-way Finite Automata ......Page 218
3.8.4 Multi-head Finite Automata ......Page 220
3.8.5 Linearly Bounded Automata ......Page 222
3.9 Exercises ......Page 226
3.10 Historical and Bibliographical References ......Page 229
4 Computers ......Page 232
4.1.1 Basic Concepts ......Page 234
4.1.2 Acceptance of Languages and Computation of Functions ......Page 235
4.1.3 Programming Techniques, Simulations and Normal Forms ......Page 238
4.1.4 Church\'s Thesis ......Page 239
4.1.5 Universal Turing Machines ......Page 241
4.1.6 Undecidable and Unsolvable Problems ......Page 244
4.1.7 Multi-tape Turing Machines ......Page 246
4.1.8 Time Speed-up and Space Compression ......Page 252
4.2.1 Basic Model ......Page 254
4.2.2 Mutual Simulations of Random Access and Turing Machines ......Page 257
4.2.3 Sequential Computation Thesis ......Page 259
4.2.4 Straight-line Programs ......Page 262
4.2.5 RRAM - Random Access Machines over Reals ......Page 266
4.3.1 Boolean Circuits ......Page 267
4.3.2 Circuit Complexity of Boolean Functions ......Page 271
4.3.3 Mutual Simulations of Turing Machines and Families of Circuits ......Page 273
4.4 PRAM - Parallel RAM ......Page 278
4.4.1 Basic Model ......Page 279
4.4.2 Memory Conflicts ......Page 280
4.4.3 PRAM Programming ......Page 281
4.4.4 Efficiency of Parallelization ......Page 283
4.4.5 PRAM Programming - Continuation ......Page 285
4.4.6 Parallel Computation Thesis ......Page 288
4.4.7 Relations between CRCW PRAM Models ......Page 292
4.5.1 Basic Concepts ......Page 294
4.5.2 Case Studies ......Page 296
4.5.3 A Normal Form ......Page 301
4.5.4 Mutual Simulations of Turing Machines and Cellular Automata ......Page 303
4.5.5 Reversible Cellular Automata ......Page 304
4.6 Exercises ......Page 305
4.7 Historical and Bibliographical References ......Page 310
5 Complexity ......Page 314
5.1 Nondeterministic Turing Machines ......Page 315
5.2 Complexity Classes, Hierarchies and Trade-offs ......Page 320
5.3 Reductions and Complete Problems ......Page 322
5.4.1 Direct Proofs of NP-completeness ......Page 325
5.4.2 Reduction Method to Prove NP-completeness ......Page 330
5.4.3 Analysis of NP-completeness ......Page 334
5.5 Average-case Complexity and Completeness ......Page 337
5.5.1 Average Polynomial Time ......Page 338
5.5.2 Reductions of Distributional Decision Problems ......Page 339
5.5.3 Average-case NP-completeness ......Page 340
5.6.1 Graph Isomorphism and Non isomorphism ......Page 341
5.6.2 Prime Recognition ......Page 342
5.7.1 Role of NP in Computing ......Page 343
5.7.3 P = NP Problem ......Page 344
5.7.4 Relativization of the P = NP Problem ......Page 346
5.7.5 P-completeness ......Page 347
5.7.6 Structure of P ......Page 348
5.7.7 Functional Version of the P = NP Problem ......Page 349
5.7.8 Counting Problems - Class #P ......Page 351
5.8.1 Performance of Approximation Algorithms ......Page 352
5.8.2 NP-complete Problems with a Constant Approximation Threshold ......Page 353
5.8.3 Traveling Salesman Problem ......Page 356
5.8.5 Complexity classes ......Page 358
5.9.1 Randomized algorithms ......Page 359
5.9.2 Models and Complexity Classes of Randomized Computing ......Page 364
5.9.3 The Complexity Class BPP ......Page 366
5.10 Parallel Complexity Classes ......Page 368
5.11 Beyond NP ......Page 369
5.11.1 Between NP and PSPACE - Polynomial Hierarchy ......Page 370
5.11.2 PSPACE-complete Problems ......Page 371
5.11.3 Exponential Complexity Classes ......Page 372
5.11.4 Far Beyond NP - with Regular Expressions only ......Page 374
5.12 Computational Versus Descriptional Complexity ......Page 375
5.13 Exercises ......Page 378
5.14 Historical and Bibliographical References ......Page 381
6 Computability ......Page 386
6.1 Recursive and Recursively Enumerable Sets ......Page 387
6.2.1 Primitive Recursive Functions ......Page 390
6.2.2 Partial Recursive and Recursive Functions ......Page 394
6.4 Undecidable Problems ......Page 399
6.4.1 Rice\'s Theorem ......Page 400
6.4.2 Halting Problem ......Page 401
6.4.3 Tiling Problems ......Page 402
6.4.4 Thue Problem ......Page 406
6.4.5 Post Correspondence Problem ......Page 407
6.4.6 Hubert\'s Tenth Problem ......Page 408
6.4.7 Borderlines between Decidability and Undecidability ......Page 410
6.4.8 Degrees of Undecidability ......Page 411
6.5 Limitations of Formal Systems ......Page 413
6.5.1 Godel\'s Incompleteness Theorem ......Page 414
6.5.2 Kolmogorov Complexity: Unsolvability and Randomness ......Page 415
6.5.3 Chaitin Complexity: Algorithmic Entropy and Information ......Page 418
6.5.4 Limitations of Formal Systems to Prove Randomness ......Page 421
6.5.5 The Number of Wisdom ......Page 423
6.5.6 Kolmogorov/Chaitin Complexity as a Methodology ......Page 426
6.6 Exercises ......Page 427
6.7 Historical and Bibliographical References ......Page 431
7 Rewriting ......Page 434
7.1 String Rewriting Systems ......Page 435
7.2 Chomsky Grammars and Automata ......Page 437
7.2.1 Chomsky Grammars ......Page 438
7.2.2 Chomsky Grammars and Turing Machines ......Page 440
7.2.3 Context-sensitive Grammars and Linearly Bounded Automata ......Page 441
7.2.4 Regular Grammars and Finite Automata ......Page 444
7.3.1 Basic Concepts ......Page 445
7.3.2 Normal Forms ......Page 449
7.3.3 Context-free Grammars and Pushdown Automata ......Page 451
7.3.4 Recognition and Parsing of Context-free Grammars ......Page 454
7.3.5 Context-free Languages ......Page 458
7.4.1 OL-systems and Growth Functions ......Page 462
7.4.2 Graphical Modeling with L-systems ......Page 465
7.5.1 Node Rewriting ......Page 469
7.5.2 Edge and Hyperedge Rewriting ......Page 471
7.6 Exercises ......Page 473
7.7 Historical and Bibliographical References ......Page 479
8 Cryptography ......Page 482
8.1.1 Cryptosystems ......Page 484
8.1.2 Cryptoanalysis ......Page 487
8.2.1 Mono-alphabetic Substitution Cryptosystems ......Page 488
8.2.2 Poly-alphabetic Substitution Cryptosystems ......Page 490
8.2.3 Transposition Cryptosystems ......Page 491
8.2.4 Perfect Secrecy Cryptosystems ......Page 492
8.2.6 DES Cryptosystem ......Page 493
8.2.7 Public Distribution of Secret Keys ......Page 495
8.3.1 Trapdoor One-way Functions ......Page 496
8.3.2 Knapsack Cryptosystems ......Page 497
8.3.3 RSA Cryptosystem ......Page 501
8.3.4 Analysis of RSA ......Page 502
8.4 Cryptography and Randomness ......Page 505
8.4.1 Cryptographically Strong Pseudo-random Generators ......Page 506
8.4.2 Randomized Encryptions ......Page 507
8.5 Digital Signatures ......Page 509
8.6 Exercises ......Page 511
8.7 Historical and Bibliographical References ......Page 514
9 Protocols ......Page 516
9.1 Cryptographic Protocols ......Page 517
9.2 Interactive Protocols and Proofs ......Page 523
9.2.1 Interactive Proof Systems ......Page 524
9.2.2 Interactive Complexity Classes and Shamir\'s Theorem ......Page 526
9.2.3 A Brief History of Proofs ......Page 531
9.3 Zero-knowledge Proofs ......Page 533
9.3.1 Examples ......Page 534
9.3.2 Theorems with Zero-knowledge Proofs ......Page 536
9.3.3 Analysis and Applications of Zero-knowledge Proofs ......Page 537
9.4 Interactive Program Validation ......Page 538
9.4.1 Interactive Result Checkers ......Page 539
9.4.2 Interactive Self-correcting and Self-testing Programs ......Page 542
9.5 Exercises ......Page 546
9.6 Historical and Bibliographical References ......Page 548
10 Networks ......Page 550
10.1.1 Networks ......Page 552
10.1.2 Basic Network Characteristics ......Page 556
10.1.3 Algorithms on Multiprocessor Networks ......Page 559
10.2.1 Information Dissemination Problems ......Page 563
10.2.2 Broadcasting and Gossiping in Basic Networks ......Page 566
10.3 Embeddings ......Page 571
10.3.1 Basic Concepts and Results ......Page 572
10.3.2 Hypercube Embeddings ......Page 575
10.4 Routing ......Page 582
10.4.1 Permutation Networks ......Page 583
10.4.2 Deterministic Permutation Routing with Preprocessing ......Page 586
10.4.3 Deterministic Permutation Routing without Preprocessing ......Page 587
10.4.4 Randomized Routing ......Page 590
10.5 Simulations ......Page 593
10.5.1 Universal Networks ......Page 594
10.5.2 PRAM Simulations ......Page 596
10.6.1 Basic Model, Problems and Layouts ......Page 598
10.6.2 General Layout Techniques ......Page 604
10.7.1 Edge Length of Regular Low Diameter Networks ......Page 609
10.7.2 Edge Length of Randomly Connected Networks ......Page 611
10.8 Exercises ......Page 613
10.9 Historical and Bibliographical References ......Page 617
11 Communications ......Page 620
11.1 Examples and Basic Model ......Page 621
11.1.1 Basic Model ......Page 625
11.2 Lower Bounds ......Page 626
11.2.1 Fooling Set Method ......Page 628
11.2.2 Matrix Rank Method ......Page 630
11.2.3 Tiling Method ......Page 631
11.2.4 Comparison of Methods for Lower Bounds ......Page 632
11.3.1 Basic Concepts and Examples ......Page 634
11.3.2 Lower Bounds - an Application to VLSI Computing ......Page 637
11.4.1 Nondeterministic Communications ......Page 640
11.4.2 Randomized Communications ......Page 644
11.5 Communication Complexity Classes ......Page 648
11.6.1 Communication Games ......Page 649
11.6.2 Complexity of Communication Games ......Page 650
11.7 Exercises ......Page 653
11.8 Historical and Bibliographical References ......Page 656
Bibliography ......Page 658
Index ......Page 686