Logic, primes and computation: a tale of unrest

• Autorzy: Leonesi S. , Toffalori C.
• Języki publikacji: EN

Abstrakty

EN

The early connections between Mathematical Logic and Computer Science date back to the thirties and to the birth itself of modern Theoretical Computer Science, and concern computability. This survey wishes to emphasize how alive and fruitful this relationship has been since then, and still is.

Słowa kluczowe

EN

computability; feasibility; primality; satisfiability

• Wydawca: Politechnika Gdańska
• Czasopismo: TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk
• Rocznik: 2005
• Tom: Vol. 9, No 3
• Strony: 273--291
• Opis fizyczny: Bibliogr. 34 poz.

Twórcy

autor

Leonesi S.

• Dipartimento di Matematica e Informatica, Universit`a di Camerino, via Madonna delle Carceri 9, 62032 Camerino, Italy

autor

Toffalori C.

• Dipartimento di Matematica e Informatica, Universit`a di Camerino, via Madonna delle Carceri 9, 62032 Camerino, Italy

Bibliografia

• [1] Herken R (Ed.) 1994 The Universal Turing Machine: A Half-Century Survey, Springer
• [2] Beeson M 1994 Computerizing Mathematics: Logic and Computation, in: [1], pp. 172–205
• [3] Davis M 1994 Mathematical Logic and the Origin of Modern Computing, in: [1], pp. 135–158
• [4] Brady A 1994 The Busy Beaver Game and the Meaning of Life, in: [1], pp. 237–254
• [5] Birkhoff G and Von Neumann J 1936 Ann. Math. 37 823
• [6] Papadimitriou C H 1994 Computational Complexity, Addison-Wesley
• [7] Sipser M 1996 Introduction to the Theory of Computation, Course Technology
• [8] Hemandspaandra L A and Ogihara M 2002 The Complexity Theory Companion, Springer
• [9] Fischer M and Rabin M 1974 Complexity of Computation, SIAM-AMS Proc. (Karp R, Ed.) 7 27
• [10] Edmonds J 1965 Can. J. Math. 17 449
• [11] Edmonds J 1967 J. Res. Nat. Bur. Standards 71B 233
• [12] Edmonds J 1967 J. Res. Nat. Bur. Standards 71B 241
• [13] Von Neumann J 1953 Contributions to the Theory of Games II (Kahn H W and Tucker A W, Eds.), Princeton University Press
• [14] Rabin M 1963 Israel J. Math. 1 203
• [15] Cobham A 1964 Proc. Int. Congress for Logic, Methodoly and Philosophhy of Science (Bar-Hillel Y, Ed.), Jerusalem, Israel, pp. 24–30
• [16] Agrawal M, Kayal N and Saxena N 2004 Ann. Math. 160 781
• [17] Granville A 2005 Bull. Amer. Math. Soc. 42 3
• [18] Bernstein D 2004 http://cr.yp.to/primetests/quartic-20040213.pdf (to appear)
• [19] Lenstra H W jr and Pomerance C 2005 http://www.math.dartmouth.edu/∼carlp/PDF/complexity12.pdf (to appear)
• [20] Shor P 1994 Proc. 35 th Ann. IEEE Symp. on Foundations of Comp. Sci., Santa Fe, NM, USA, pp. 20–22
• [21] Garey M and Johnson D 1979 Computers and Intractability: A Guide to the Theory of Completeness, Freeman
• [22] Johnson D 1990 Handbook of Theoretical Computer Science – A: Algorithms and Complexity (Van Leeuwen J, Ed.), Elsevier, pp. 67–161
• [23] Miller G 1976 J. Comput. System Sci. 13 300
• [24] Rabin M 1980 J. Number Theory 12 128
• [25] Lautemann C 1983 Information Processing Letters 17 215
• [26] Sipser M 1983 Proc. 15 th ACM Symp. Theory of Computing, Boston, MA, USA, pp. 330–335
• [27] Valiant L and Vazirani V 1986 Theor. Comp. Sci. 47 85
• [28] Stockmeyer L 1973 Proc. 5 th Ann. ACM Symp. on Theory of Computing, Austin, TX, USA, pp. 1–9
• [29] Babai L and Moran S 1988 J. Comput. System Sci. 36 254
• [30] Goldwasser S, Micali S and Rackoff C 1985 Proc. 17 th ACM Symp. on Theory of Computing, Providence, RI, USA, pp. 291–304
• [31] Shamir A 1992 J. Ass. Comput. Mach. 39 869
• [32] Baker T, Gill J and Solovay R 1975 SIAM J. Comput. 4 431
• [33] Fagin R 1974 Complexity of Computation, SIAM-AMS Proc. (Karp R, Ed.) 7 43
• [34] Immerman N 1983 Proc. 15 th ACM Symp. on Theory of Computing, Boston, MA, USA, pp. 347–354