Linked bibliography for the SEP article "Computability and Complexity" by Neil Immerman

This is an automatically generated and experimental page

If everything goes well, this page should display the bibliography of the aforementioned article as it appears in the Stanford Encyclopedia of Philosophy, but with links added to PhilPapers records and Google Scholar for your convenience. Some bibliographies are not going to be represented correctly or fully up to date. In general, bibliographies of recent works are going to be much better linked than bibliographies of primary literature and older works. Entries with PhilPapers records have links on their titles. A green link indicates that the item is available online at least partially.

This experiment has been authorized by the editors of the Stanford Encyclopedia of Philosophy. The original article and bibliography can be found here.

Allender, E., M. Bauland, N. Immerman, H. Schnoor and H. Vollmer, 2009, “The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem”, Journal of Computer and System Science 75(4): 245–254. (Scholar)
Arora, Sanjeev and Boaz Barak, 2009, Computational Complexity: A Modern Approach, New York: Cambridge University Press. (Scholar)
Böerger, Egon, Erich Grädel, and Yuri Gurevich, 1997, The Classical Decision Problem, Heidelberg: Springer. (Scholar)
Bulatov, Andrei, 2017, “A Dichotomy Theorem for Nonuniform CSPs”, IEEE 58th Annual Symposium on Foundations of Computer Science, 319–330. (Scholar)
–––, 2018, “Constraint Satisfaction Problems: Complexity and Algorithms”, SIGLOG News 4(5): 3–24. (Scholar)
Church, Alonzo, 1933, “A Set of Postulates for the Foundation of Logic (Second Paper)”, Annals of Mathematics (Second Series), 33: 839–864. (Scholar)
–––, 1936a, “An Unsolvable Problem of Elementary Number Theory,” American Journal of Mathematics, 58: 345–363. (Scholar)
–––, 1936b, “A Note on the Entscheidungsproblem,” Journal of Symbolic Logic, 1: 40–41; correction 1, 101–102. (Scholar)
Cobham, Alan, 1964, “The Intrinsic Computational Difficulty of Functions,” Proceedings of the 1964 Congress for Logic, Mathematics, and Philosophy of Science, Amsterdam: North-Holland, pp. 24–30. (Scholar)
Cook, Stephen, 1971, “The Complexity of Theorem Proving Procedures,” Proceedings of the Third Annual ACM STOC Symposium, Shaker Heights, Ohio, pp. 151–158. (Scholar)
Davis, Martin, 2000, The Universal Computer: the Road from Leibniz to Turing, New York: W. W. Norton & Company. (Scholar)
Edmonds, Jack, 1965, “Paths, Trees and Flowers,” Canadian Journal of Mathematics, 17: 449–467. (Scholar)
Enderton, Herbert B., 1972, A Mathematical Introduction to Logic, New York: Academic Press. (Scholar)
Fagin, Ronald, 1974, “Generalized First-Order Spectra and Polynomial-Time Recognizable Sets,” in Complexity of Computation, R. Karp (ed.), SIAM-AMS Proc, 7: 27–41. (Scholar)
Feder, Tomas and Moshe Vardi, 1999, “The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study Through Datalog and Group Theory”, SIAM Journal of Computing 28: 57–104. (Scholar)
Garey, Michael and David S. Johnson, 1979, Computers and Intractability, New York: Freeman. (Scholar)
Gödel, Kurt, 1930, “The Completeness of the Axioms of the Functional Calculus,” in van Heijenoort 1967: 582–591. (Scholar)
–––, 1931, “On Formally Undecidable Propositions of Principia Mathematica and Related Systems I,” in van Heijenoort, 1967: 592–617. (Scholar)
Hartmanis, Juris, 1989, “Overview of computational Complexity Theory” in J. Hartmanis (ed.), Computational Complexity Theory, Providence: American Mathematical Society, pp. 1–17. (Scholar)
Hilbert and Ackermann, 1928/1938, Grundzüge der theoretischen Logik, Springer. English translation of the 2nd edition: Principles of Mathematical Logic, New York: Chelsea Publishing Company, 1950. (Scholar)
Hodges, Andrew, 1992, Alan Turing: the Enigma, London: Random House. (Scholar)
Hofstadter, Douglas, 1979, Gödel, Escher, Bach: an Eternal Golden Braid, New York: Basic Books. (Scholar)
Hopcroft, John E., 1984, “Turing Machines”, Scientific American, 250(5): 70–80. (Scholar)
Immerman, Neil, 1999, Descriptive Complexity, New York: Springer. (Scholar)
Jeavons, P.G., D.A. Cohen and M. Gyssens, 1997, “Closure Properties of Constraints”, Journal of the ACM, 44: 527–548. (Scholar)
Jones, Neil, 1973, “Reducibility Among Combinatorial Problems in Log n Space”, Proc. Seventh Annual Princeton Conf. Info. Sci. and Systems, 547–551. (Scholar)
Karp, Richard, 1972, “Reducibility Among Combinatorial Problems,”, in Complexity of Computations, R.E. Miller and J.W. Thatcher (eds.), New York: Plenum Press, pp. 85–104. (Scholar)
Kleene, Stephen C., 1935, “A Theory of Positive Integers in Formal Logic,” American Journal of Mathematics, 57: 153–173, 219–244. (Scholar)
–––, 1950, Introduction to Metamathematics, Princeton: Van Nostrand. (Scholar)
Ladner, Richard, 1975, “On the structure of polynomial time reducibility”, Journal of the ACM, 155–171. (Scholar)
Levin, Leonid, 1973, “Universal search problems,” Problemy Peredachi Informatsii, 9(3): 265–266; partial English translation in B.A.Trakhtenbrot, 1984, “A Survey of Russian Approaches to Perebor (Brute-force Search) Algorithms,” IEEE Annals of the History of Computing, 6(4): 384–400. (Scholar)
Markov, A.A., 1960, “The Theory of Algorithms,” American Mathematical Society Translations (Series 2), 15: 1–14. (Scholar)
Meyer, Albert and Dennis Ritchie, 1967, “The Complexity of Loop Programs,” Proceedings of the 22nd National ACM Conference, Washington, D.C., 465–470. (Scholar)
Nordström, Jakob, 2015, “On the Interplay Between Proof Complexity and SAT Solving,” SIGLOG News, 2(3): 18–44. (Scholar)
Papadimitriou, Christos H., 1994, Computational Complexity, Reading, MA: Addison-Wesley. (Scholar)
Péter, Rózsa. 1967, Recursive Functions, translated by István Földes, New York: Academic Press. (Scholar)
Post, Emil, 1936, “Finite Combinatory Processes – Formulation I,” Journal of Symbolic Logic, 1: 103–105. (Scholar)
Rogers, Hartley Jr., 1967, Theory of Recursive Functions and Effective Computability, New York: McGraw-Hill. (Scholar)
Schaefer, Thomas, 1978, “The Complexity of Satisfiability Problems”, Proceedings of the Tenth Annual ACM STOC Symposium, 216–226. (Scholar)
Skolem, Thoralf, 1923, “The foundations of elementary arithmetic established by means of the recursive mode of thought,” in van Heijenoort 1967: 302–33. (Scholar)
Turing, A. M., 1936–7, “On Computable Numbers, with an Application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society, 2(42): 230–265 [Preprint available online]. (Scholar)
Valiant, Leslie, 1982, “Reducibility By Algebraic Projections”, L’Enseignement mathematique, 28(3–4): 253–268. (Scholar)
van Heijenoort, Jean, (ed.), 1967, From Frege To Gödel: A Source Book in Mathematical Logic, 1879–1931, Cambridge, Massachusetts: Harvard University Press. (Scholar)
Whitehead, Alfred North and Bertrand Russell, 1910–1913, Principia Mathematica, first edition, Cambridge: Cambridge University Press. (Scholar)
Zhuk, Dmitriy, 2020, “A Proof of CSP Dichotomy Conjecture”, Journal of the ASM, 30: 1–78. (Scholar)

Generated Sun Sep 15 11:15:22 2024

Applied ethics	Epistemology	History of Western Philosophy	Meta-ethics	Metaphysics	Normative ethics
Philosophy of biology	Philosophy of language	Philosophy of mind	Philosophy of religion	Science Logic and Mathematics	More ...