Leonid A. Levin. Fundamentals of Computing.

The HTML , PDF , Postscript , and DVI files.

The LaTeX sources:

    Foreword.
  1. Models of Computations; Polynomial Time and Church's Thesis.
    1. Deterministic Computation.
    2. Rigid Models.
    3. Pointer Machines.
    4. Simulation.
  2. Universal Algorithm; Diagonal Results.
    1. Universal Turing Machine.
    2. Uncomputability; Goedel Theorem.
    3. Intractability; Compression and Speed-up Theorems.
  3. Games; Alternation; Exhaustive Search; Time v. Space.
    1. How to Win.
    2. Exponentially Hard Games.
    3. Reductions; Non-Deterministic and Alternating TM; Time/Space.
    4. Fast and Lean Computations.
  4. Nondeterminism; Inverting Functions; Reductions.
    1. Example of a Narrow Computation: Inverting a Function.
    2. Complexity of NP Problems.
    3. An NP-Complete Problem: Tiling.
  5. Randomness in Computing.
    1. A Monte-Carlo Primality Tester.
    2. Randomized Algorithms and Random Inputs.
    3. Randomness and Complexity.
    4. Pseudo-randomness.
    5. Cryptography.
References.

You can also click for my papers (some online), my C V, or my research overview.

This material is based upon work supported by the National Science Foundation under Grants No.8304498, 8607492, 9015276, 9610455, 9820934, 0311411, 0830719. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.