The HTML , PDF , Postscript , and DVI files.
The LaTeX sources:
Foreword.
- Models of Computations; Polynomial Time and Church's Thesis.
- Deterministic Computation.
- Rigid Models.
- Pointer Machines.
- Simulation.
- Universal Algorithm; Diagonal Results.
- Universal Turing Machine.
- Uncomputability; Goedel Theorem.
- Intractability; Compression and Speed-up
Theorems.
- Games; Alternation; Exhaustive Search; Time v. Space.
- How to Win.
- Exponentially Hard Games.
- Reductions; Non-Deterministic and Alternating
TM; Time/Space.
- Nondeterminism; Inverting Functions; Reductions.
- Example of a Narrow Computation: Inverting a Function.
- Complexity of NP Problems.
- An NP-Complete Problem: Tiling.
- Randomness in Computing.
- A Monte-Carlo Primality Tester.
- Randomized Algorithms and Random Inputs.
- Randomness and Complexity.
- Pseudo-randomness.
- 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.