Contents

• Acknowledgments.
• 1 Models of Computations; Polynomial Time & Church's Thesis.
  • 1.1 Deterministic Computation.
    • Complexity.
      • Growth Rate Notations:
  • 1.2 Rigid Models.
    • Cellular Automata (CA).
    • An example: the Game of Life (GL).
    • Turing Machines.
      • Problem:
  • 1.3 Pointer Machines.
    • Example Problem.
  • 1.4 Simulation.
    • PKM Simulation of PPM.
    • TM Simulation of PPM.
    • FCM Simulation of PPM
    • Batcher Merge:
• 2 Universal Algorithm; Diagonal Results.
  • 2.1 Universal Turing Machine.
  • 2.2 Uncomputability; Goedel Theorem.
    • Universal and Complete Functions.
    • Goedel Theorem.
      • Recursive Functions.
  • 2.3 Intractability; Compression and Speed-up Theorems.
    • Speed-up Theorem.
• 3 Games; Alternation; Exhaustive Search; Time v. Space.
  • 3.1 How to Win.
  • 3.2 Exponentially Hard Games.
    • Exptime Complete Halting Game.
      • Strategy:
  • 3.3 Reductions; Non-Deterministic and Alternating TM; Time and Space.
    • Linear Chess Simulation of TM-Game.
    • A Question Still Open: Space-Time Trade-off.
      • Can every narrow computation be converted into a compact one?
  • 3.4 Fast and Lean Computations.
    • Parallelization.
    • Computing in Tight Space: a Pebble Game.
• 4 Nondeterminism; Inverting Functions; Reductions.
  • 4.1 Example of a Narrow Computation: Inverting a Function.
    • Search and NP Problems.
  • 4.2 Complexity of NP Problems.
    • NP-Completeness
  • 4.3 An NP-Complete Problem: Tiling.
    • Padding Argument.
    • The Reduction.
    • Proof.
• 5 Randomness in Computing.
  • 5.1 A Monte-Carlo Primality Tester.
    • Residue Arithmetic.
    • Fermat Test.
    • Square Root Test.
    • Rabin-Miller Test.
  • 5.2 Randomized Algorithms and Random Inputs.
    • Random Inputs
    • Symmetry Breaking.
  • 5.3 Randomness and Complexity.
    • Kolmogorov Complexity
    • Deficiency of Randomness.
      • Rectification of Distributions.
  • 5.4 Pseudo-randomness.
    • Hard Core.
  • 5.5 Cryptography.
    • Public Key Encryption.
    • Go On!
      • Writing Contributions.
• References
• About this document ...