\newpage \begin {thebibliography} {99}

\bibitem{alg} T.H. Cormen, C.E. Leiserson, R.L. Rivest.
 Introduction to Algorithms. 1990, McGraw-Hill.

\bibitem{Knuth} Donald E. Knuth. {\em The Art of Computer Programming.}
Vol.~1-3. Addison-Wesley, 3d ed., 1997. Additions to v.2 can be found in
\href {http://www-cs-faculty.stanford.edu/~knuth/err2-2e.ps.gz}
{http://www-cs-faculty.stanford.edu/\~{}knuth/err2-2e.ps.gz} .

 \bibitem{feller} William Feller. {\em An Introduction to Probability Theory
and Its Applications.} John Wiley \& Sons, 1968.

 \bibitem{Lang} S.~Lang. {\em Algebra.} 3rd ed. 1993, Addison-Wesley.

 \bibitem{rg} H. Rogers, Jr. {\em Theory of Recursive Functions and
Effective Computability.} McGraw-Hill Book Co., 1967.

\bibitem[]{sec1} References for section~\ref{models}:

\bibitem{ba} Ja.M. Barzdin', Ja.Ja. Kalnin's.
 A Universal Automaton with Variable Structure.
 {\em Automatic Control and Computing Sciences.} 8(2):6-12, 1974.

 \bibitem{ww} E.R. Berlekamp, J.H. Conway, R.K. Guy. {\em Winning Ways.}
Section 25. Academic Press, 1982.

 \bibitem{ku} A.N. Kolmogorov, V.A. Uspenskii. On the Definition of an
Algorithm. {\em Uspekhi Mat. Nauk} 13:3-28, 1958; AMS Transl.\ 2nd ser.\
29:217-245, 1963.

 \bibitem{pm} A. Schoenhage. Storage Modification Machines.
 {\em SIAM J. on Computing} 9(3):490-508, 1980.

 \bibitem{ofm} Yu. Ofman. A Universal Automaton.
 {\em Transactions of the Moscow Math. Society,} pp.200-215, 1965.

\bibitem[]{sec2} Section~\ref{diagonal}:

 \bibitem{spd} M. Blum. A machine-independent theory of the complexity of
recursive functions. {\em J. ACM} 14, 1967.

 \bibitem{und} M. Davis, ed. {\em The Undecidable.} Hewlett, N.Y. Raven Press,
1965.\\ (The reprints of the original papers of K.Goedel, A.Turing, A.Church,
E.Post and others).

 \bibitem{Ikeno} Shinichi Ikeno. A 6-symbol 10-state Universal Turing Machine.
 {\em Proc.~Inst.~of Elec.~Comm.} Tokyo, 1958.

\bibitem{sm} Joel I. Seiferas, Albert R. Meyer. Characterization of Realizable
Space Complexities.\\ {\em Annals of Pure and Applied Logic} 73:171-190, 1995.

 \bibitem{rb} M.O. Rabin. Speed of computation of functions and classification
of recursive sets. {\em Third Convention of Sci.Soc.} Israel, 1959, 1-2.
Abst.: Bull. of the Research Council of Israel, 8F:69-70, 1959.

 \bibitem{ts} G.S. Tseitin. Talk: seminar on math. logic, Moscow university,
 11/14, 11/21, 1956. Also pp.~44-45 in: S.A. Yanovskaya,
 Math.~Logic and Foundations of Math., {\em Math.~in the USSR for 40 Years,}
 1:13-120, 1959, Moscow, Fizmatgiz, (in Russian).

 % 90 min TV movie about Alan Turing: "Breaking The Code," 1997, VHS.
 % http://www.amazon.com/exec/obidos/ASIN/6304361092/

\bibitem[]{sec3} Section~\ref{games}:

 \bibitem{1} J. v.Neumann, O. Morgenstern. {\em Theory of Games and Economic
Behavior}. Princeton Univ. Press, 1944.

 \bibitem{2} A.K.Chandra and L.J.Stockmeyer, Alternation. {\em FOCS}-1976.

 \bibitem{4} Ashok K. Chandra, Dexter C. Kozen, Larry J. Stockmeyer.
Alternation. {\em J. ACM}, 28(1):114-133, 1981.

 \bibitem{checkers} J.M. Robson. N by N checkers is EXPTIME-complete.
	{\em SIAM J. Comput} 13(2), 1984.

 \bibitem{go} J.M. Robson. The complexity of Go.
	{\em Proc. 1983 IFIP World Computer Congress}, p.~413-417.

 \bibitem{chess} A.S. Fraenkel and D. Lichtenstein. Computing a perfect
strategy for $n\times n$ chess requires time exponential in $n$.
 {\em J. Combin. Theory\/} (Ser.~A) 31:199-214. ICALP-1981.

\bibitem[]{sec4} Section~\ref{np}:

 \bibitem{7} W.J. Savitch. Relationships between nondeterministic and
deterministic tape complexities. {\em J. Comput. Syst. Sci.} 4:177-190, 1970.

\bibitem{YN} D.B. Yudin and A.S. Nemirovsky. Informational Complexity and
Effective Methods for Solving Convex Extremum Problems. {\em Economica i Mat.
Metody} 12(2):128-142; transl. {\em MatEcon} 13:3-25, 1976.

\bibitem{8} E.M. Luks: Isomorphism of Graphs of Bounded Valence Can Be Tested
in Polynomial Time. {\em FOCS}-1980.

\bibitem{GJ} M.R.Garey, D.S.Johnson. {\em Computers and Intractability.}
W.H.Freeman \& Co. 1979.

 \bibitem{trakh} B.A.Trakhtenbrot. A survey of Russian approaches to
 {\em Perebor} (brute-force search) algorithms.
 {\em Annals of the History of Computing,} 6(4):384-400, 1984.

\bibitem[]{sec5} Section~\ref{rand}:

 \bibitem{14} M.O.Rabin. Probabilistic Algorithms for Testing Primality.
 {\em J. Number Theory}, 12: 128-138, 1980.

 \bibitem{15} G.L.Miller. Riemann's Hypothesis and tests for Primality.
 {\em J.~Comp.~Sys.~Sci.} 13(3):300-317, 1976.

 \bibitem{16} R. Solovay, V. Strassen. A fast Monte-Carlo test for primality.
 {\em SIComp} 6:84-85, 1977.

 \bibitem{12} R. Karp. Combinatorics, Complexity and Randomness. (Turing Award
Lecture) {\em Communication of the ACM}, 29(2):98-109, 1986.

 \bibitem{17} David S. Johnson. The NP-Completeness Column.
 {\em J. of Algorithms} 5, (1984) 284-299.

 \bibitem{karp-pr} R. Karp. The probabilistic analysis of some combinatorial
search algorithms. {\em Algorithms and Complexity.} (J.F.Traub, ed.)
 Academic Press, NY 1976, pp. 1-19.

 \bibitem{18} Y. Gurevich, Average Case Complexity, Internat. Symp.\ on
Information Theory, IEEE, Proc.\ 1985.

\bibitem{ku87} A.N.Kolmogorov, V.A.Uspenskii. Algorithms and Randomness.
 {\em Theoria Veroyatnostey i ee Primeneniya = Theory of Probability and its
Applications}, 3(32):389-412, 1987.

 \bibitem{vitan} M. Li, P.M.B. Vitanyi. Introduction to Kolmogorov Complexity
and its Applications. Springer Verlag, New York, 1993.

 \bibitem{22} M. Blum, S. Micali. How to generate Cryptographically Strong
Sequences. {\em SIAM J. Comp.}, 13, 1984.

 \bibitem{24} A. C. Yao. Theory and Applications of Trapdoor Functions. {\em
FOCS}-1982.

 \bibitem{25} O.Goldreich, L.Levin. A Hard-Core Predicate for all One-Way
Functions. {\em STOC}-1989, pp. 25-32.

 \bibitem{26} R.Rivest, A.Shamir, L.Adleman. A Method for Obtaining Digital
Signature and Public-Key Cryptosystems. {\em Comm. ACM}, 21:120-126, 1978.

 \bibitem{27} M. Blum, S. Goldwasser. An Efficient Probabilistic
Encryption Scheme Hiding All Partial Information. {\em Crypto}-1982.

 \bibitem{29} M. Rabin. {\em Digitalized Signatures as Intractable as
Factorization.} MIT/LCS/TR-212, 1979.

\bibitem{color} R.Venkatesan, L.Levin. Random Instances of a Graph Coloring
Problem are Hard. {\em STOC}-1988.

 % \bibitem{causal} Peter Gacs, Leonid A. Levin. Causal Nets or What Is
 % a Deterministic Computation? {\em Information and Control} 51(1), 1981.
 % \bibitem{min} M.L. Minsky. {\em Computation: Finite and Infinite Machines.}
 % Prentice-Hall, Englewood Cliffs, N.J., 1967.
 % \bibitem{Shannon} C.E.Shannon: Automata Studies. 157-165, 1956.
 %\bibitem{tur} A.M.Turing : Proc. London Math. Soc. Ser. 2, 42, 230-265, 1936.
 % \bibitem{fct} L.~Levin. On Storage Capacity for Algorithms.
 % {\em Soviet Math.\ Dokl.} 14(5):1464-1466, 1973.
 % \bibitem{9} S. Cook. The complexity of theorem proving procedures.
 % {\em STOC}, 1971.
 % \bibitem{11} R. Karp. Reducibility among combinatorial problems.
 % {\em Complexity of Computer Computations.}
 % R. Miller, J. Thatcher eds. Plenum, NY, 1972, pp. 85-103.
 % \bibitem{search} L.Levin, Universal Sequential Search Problems, {\em Probl.\
 % Pered.\ Inf.\ = Probl.\ Inform.\ Transm.} 9(3), 1973.
 % \bibitem{19} A.N. Kolmogorov. Three Approaches to the Concept of the Amount
 % of Information. {\em Probl. Inf. Transm.} 1(1), 1965.
 % \bibitem{20} P. Martin-Lof. The Definition of Random Sequences.
 % {\em Inf. and Control} 9:602-619, 1966.
 % \bibitem{21} R.J. Solomonoff. A Formal Theory of Inductive Inference.
 % {\em Inf. and Control} 7(1):l-22, 1964.
 % \bibitem{23} O. Goldreich, S. Goldwasser, S. Micali.
 %  How to Construct Random Functions. {\em J. ACM}, 33(4), 1986.

 \end {thebibliography}
 \end {document}