1755 P. Alexandrov (ed.): Die Hilbertschen Probleme. Leipzig 1983. Saneev Arora/Shmuel Safra: Probabilistic checking of proofs - a new characterization of NP. J. ACM 45/1 (1998), 70-122. Saneev Arora/Carsten Lund/Rajeev Motwani/Madhu Sudan/Mario Szegedy: Proof verification and hardness of approximation problems. J. ACM 45/3 (1998), 501-555. J. Balcazar/J. Diaz/J. Gabarro: Structural complexity I. Springer 1994, 200p. 3-540-58384-X. DM 58. 10887 Ron Bartlett: Functions, languages, and machines. Internet 1996, 180p. Contents: Sets, functions, and countability; Languages, grammars, and computability; Finite-state machines and regular grammars; Decidable properties of regular languages; Push-down auotmata and context-free grammars; Decidable properties of context-free languages; Turing machines and unrestricted grammars; Undecidable properties of unrestricted languages; Turing machine complexity classes; Recursive functions; Cellular automata; neural networks. L. Blum/F. Cucker/M. Shub/S. Smale: Complexity and real computation. Springer 1997, 430p. 3-540-98281-7. DM 79. 2179 Egon Boerger: Berechenbarkeit, Komplexitaet, Logik. Vieweg 1986. Manfred Bretz: Algorithmen und Berechenbarkeit. Vieweg 1992, 180p. 3-528-05233-3. DM 34. P. Bürgisser: Completeness and reduction in algebraic complexity theory. Springer 2000, 170p. DM 129. P. Bürgisser/M. Clausen/M. Shokrollahi: Algebraic complexity theory. Springer 1997, 620p. 3-540-60582-7. DM 188. 16390 Gregory Chaitin: Grenzen der Berechenbarkeit. Spektrum Februar 2004, 86-93. A. Chandra/L. Stockmeyer/U. Vishkin: Constant depth reducibility. SIAM J. Computing 13 (1984), 423-439. Stephen Cook: The complexity of theorem-proving procedures. Proc. 3rd Annual ACM Symp. Theory of Computing (1971), 151-158. Stephen Cook: Deterministic CFLs are accepted simultaneously in polynomial time and log squared space. 11th Symp. Theory Comp. 1979, 338-345. Stephen Cook: Towards a complexity theory of synchronous parallel computation. Symp. Logic and Algorithmic 1980, 75-100. Nigel Cutland: Computability. Cambridge UP 1980, 260p. $28. 3187 Martin Davis: Computability and unsolvability. Dover 1982, 250p. V. Detlovs: Equivalence of normal algorithms and recursive functions. Trudy Mat. Inst. Steklov 52 (1958), 75-139. 14409 Michael Drmota: Sieben Millenniumsprobleme I. IMN 184 (2000), 29-36. Das P-NP-Problem, die Riemannsche Vermutung, die Vermutung von Birch-Swinnerton-Dyer. 14313 Ronald Fagin: Finite model theory - a personal perspective. Theor. Comp. Sci. 116 (1993), 3-31. 14334 Ronald Fagin: Generalized first-order spectra and polynomial-time recognizable sets. In Karp 1974, 43-73. 10829 Ronald Fagin: Easier ways to win logical games. Descriptive Complexity and Finite Models 1 (1997), 1-32. Walter Felscher: Berechenbarkeit. Springer 1993, 480p. DM 48. 11230 Stephen Fenner/Lance Fortnow/Ashish Naik/John Rogers: Inverting onto functions. Internet ca. 1996, 13p. M. Garey/D. Johnson: Computers and intractability. A guide to the theory of NP-completeness. Freeman 1979. Oded Goldreich: Computational complexity. Cambridge UP 2008. 27180 W. T. Gowers: Razborov's method of approximations. Internet ca. 2010, 21p. 17945 Martin Grötschel: P = NP? Elem. Math. 57 (2002), 96-102. R. Herken (ed.): The universal Turing machine. A half-century survey. Kammerer & Unverzagt 1988. 12094 Hans Hermes: Aufza''hlbarkeit, Entscheidbarkeit, Berechenbarkeit. Springer 1961. 12120 Steven Homer: The isomorphism conjecture and its generalizations. In 4917 Odifreddi, 1-11. 14319 Neil Immerman: Descriptive complexity - a logician's approach to computation. Notices AMS October 1995, 1127-1133. Neil Immerman: Descriptive complexity. Springer 1998, 300p. DM 147. 14320 Neil Immerman: The computational complexity column. Internet ca. 2000, 12p. Richard Karp: Reducibility among combinatorial problems. In Miller/Thatcher 1972, 85-103. Richard Karp (ed.): Complexity of computation. SIAM-AMS Proc. 7 (1974). 7959 Joerg Keller/Wolfgang Paul: Hardwaredesign. Teubner 1995, 420p. 3-8154-2065-2. DM 60. J. Koebler/U. Schoening/T. Jacobo: The graph isomorphism problem. Its structural complexity. Birkhaeuser 1993, 160p. DM 65. Harry Lewis/Christos Papadimitriou: Elements of the theory of complexity. Prentice Hall 1981. M. Li/P. Vitanyi: An introduction to Kolmogorov complexity and its applications. Springer 1993, 550p. 3-540-94053-7. $60. 21866 Heinz Lüneburg: Rekursive Funktionen. Springer 2002, 86p. Eur 24. O. Lupanov: Complexity of formula realization of functions of logical algebra. Prob. Cybern. 3 (1962), 782-811. 17995 K. Meer: Besprechung des Buches "Komplexitätstheorie" von Ingo Wegener. Jber. DMV 108/2 (2006), B 5-6. Kurt Mehlhorn: Graph Algorithms and NP-Completeness. Springer 1984. R. Miller/J. Thatcher (ed.): Complexity of computer computation. Plenum Press 1972. 25473 Marvin Minsky: Recursive unsolvability of Post's problem of tag and other topics in theory of Turing machines. Ann. Math. 74/3 (1961), 437-455. 25474 Liesbeth de Mol: Tag systems and Collatz-like functions. Theor. Comp. Sci. 390 (2008), 92-101. 5153 Eddie Morris/Leon Harkleroad: Rozsa Peter: Recursive functions theory's founding mother. Math. Intell. 12/1 (19907, 59-61. Jan Mycielski a.o. (ed.): Structures in logic and computer science. Springer LN CS 1261 (1997). Arnold Oberschelp: Rekursionstheorie. Bibl. Inst. 1993, 300p. 3-411-16171-X. DM 30. Piergiorgio Odifreddi: Classical recursion theory. 2 volumes. 24775 Jaap van Oosten: Basic computability theory. Univ. Utrecht 2013, 87p. Christos Papadimitriou: Computational complexity. Addison-Wesley 1994. 5768 Wolfgang Paul: Komplexitaetstheorie. Teubner 1978. Nicholas Pippenger: On simultaneous resource bounds. 20th Symp. Found. Computer Science 1979, 307-311. Nicholas Pippenger: Theories of computability. Cambridge UP 1997. $50. 18842 Jaikumar Radhakrishnan/Madhu Sudan: On Dinur's proof of the PCP theorem. Bull. AMS 44/1 (2007), 19-61. N. Redkin: Minimal realization of a binary adder. Probl. Kibern. 38 (1981), 181-216, 272. Ru''diger Reischuk: Komplexita''tstheorie. 2 volumes. Teubner 1998+1999, 300+300p. 3-519-12275-8, 02285-0. DM 55+XX. 17733 Hartley Rogers: Theory of recursive functions and effective computatbility. MIT Press 1987, 500p. Eur 40. J. Rosser: Highlights of the history of the lambda-calculus. Annals of the History of Computing 6 (1984), 337-349. Peter Sander/Wolffried Stucky/Rudolf Herschel: Automaten - Sprachen - Berechenbarkeit. Teubner 1995, 270p. 3-519-12937-X. DM 43. John Savage: Models of computation. Addison-Wesley 1998. 7927 Claus Peter Schnorr: Rekursive Funktionen und ihre Komplexitaet. Teubner 1974. Robert Sedgewick/Philippe Flajolet: An introduction to the analysis of algorithms. Addison-Wesley 490p. $55. 24396 Joseph Shoenfield: Review of the book "Classical recursion theory" by Piergiorgio Odifreddi. Bull. AMS 28/1 (1993), 182-183. Joseph Shoenfield: Recursion theory. Springer 1993, 100p. 3-540-57093-4. DM 44. 5651 Guglielmo Tamburrini: Tesi di Church-Turing e problema mente-macchina. Lettera Pristem 8 (1993), 14-19. 5531 Joseph Traub/Henryk Wozniakowski: Information-based complexity. New questions for mathematicians. Math. Intell. 13/2 (1991), 34-43. 6480 Joseph Traub/Henryk Wozniakowski: Wege aus der Unberechenbarkeit. Spektrum 1994/4, 64-69. 13604 Heribert Vollmer: Was leistet die Komplexita''tstheorie fu''r die Praxis? Informatik-Spektrum Oktober 1999, 317-327. O. Watanabe (ed.): Kolmogorov complexity and computational complexity. Springer 1992, 110p. 3-540-55840-3. DM 48. Ingo Wegener: Komplexitätstheorie. Springer 2003, 320p. Eur 30. 5767 Klaus Weihrauch: Computability. Springer 1987. 5939 D. Welsh: Complexity: Knots, colourings and countings. Cambridge UP 1993. 0-521-45740-8.