Linked bibliography for the SEP article "Computational Complexity Theory" by Walter Dean

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.

  • Aaronson, S., 2003, “Is P Versus NP Formally Independent?” Bulletin of the EATCS, 81: 109–136. (Scholar)
  • –––, 2005, “NP-complete problems and physical reality,” ACM Sigact News, 36(1): 30–52.
  • –––, 2013a, Quantum Computing Since Democritus, Cambridge, England: Cambridge University Press. (Scholar)
  • –––, 2013b, “Why Philosophers Should Care About Computational Complexity,” in J. Copeland, C. Posy, & O. Shagrir (eds.), Computability: Turing, Gödel, Church, and Beyond, pp. 261–328, Cambridge, Massachusetts: MIT Press. (Scholar)
  • Ackermann, W., 1928, “Über die Erfüllbarkeit gewisser Zählausdrücke,” Mathematische Annalen, 100(1): 638–649. (Scholar)
  • Agrawal, M., Kayal, N., and Saxena, N., 2004, “PRIMES in P,” Annals of Mathematics. Second Series, 160(2): 781–793.
  • Allender, E., and McCartin, C., 2000, “Basic Complexity,” in R. Downey & D. Hirschfeldt (eds.), Aspects of Complexity, pp. 1–28, Berlin: Walter de Gruyter. (Scholar)
  • Arora, S., and Barak, B., 2009, Computational Complexity: A Modern Approach, Cambridge, England: Cambridge University Press. (Scholar)
  • Artemov, S., and Kuznets, R., 2014, “Logical Omniscience as infeasibility,” Annals of Pure and Applied Logic, 165: 6–25. (Scholar)
  • Baker, T., Gill, J., and Solovay, S., 1975, “Relativizations of the \(\textbf{P} = \textbf{NP}?\) question,” SIAM Journal on Computing, 4(4): 431–442. (Scholar)
  • Balcázar, J., Diaz, J., and Gabarró, J., 1988, Structural Complexity Vol. I, Berlin: Springer Verlag. (Scholar)
  • Bellantoni, S., and Cook, S., 1992, “A new recursion-theoretic characterization of the polytime functions,” Computational Complexity, 2(2): 97–110.
  • Bellman, R., 1962, “Dynamic Programming Treatment of the Travelling Salesman Problem,” Journal of the ACM, 9: 61–63. (Scholar)
  • Ben-David, S., and Halevi, S., 1992, On the Independence of P Versus NP (No. 714), Technion. (Scholar)
  • Bennett, J., 1962, On Spectra (PhD thesis), Princeton. (Scholar)
  • Bernays, P., 1935, “Sur Le Platonisme Dans Les Mathématiques.” L’enseignement Mathematique, 34: 52–69. (Scholar)
  • Bernays, P., and Schönfinkel, M., 1928, “Zum Entscheidungsproblem der Mathematischen Logik,” Mathematische Annalen, 99(1): 342–372. (Scholar)
  • Bonet, M., Buss, S., and Pitassi, T., 1995, “Are there hard examples for Frege systems?” in Feasible Mathematics II, pp. 30–56, Berlin: Springer. (Scholar)
  • Brookshear, J., Smith, D., Brylow, D., Mukherjee, S., and Bhattacharjee, A., 2006, Computer Science: An Overview 9th ed., Boston: Addison-Wesley. (Scholar)
  • Buss, S., 1986, Bounded Arithmetic, Naples: Bibliopolis. (Scholar)
  • –––, 1987, “The Boolean formula value problem is in ALOGTIME,” in Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 123–131. (Scholar)
  • –––, 1999, “Propositional Proof Complexity an Introduction,” in Computational Logic, pp. 127–178, Springer. (Scholar)
  • –––, 2012, “Towards NP–P via Proof Complexity and Search,” Annals of Pure and Applied Logic, 163(7): 906–917. (Scholar)
  • Carbone, A., and Semmes, S., 1997, “Making Proofs Without Modus Ponens: An Introduction to the Combinatorics and Complexity of Cut Elimination,” Bulletin of the American Mathematical Society, 34(2): 131–159. (Scholar)
  • Chagrov, A., 1985, “On the Complexity of Propositional Logics,” in Complexity Problems in Mathematical Logic, pp. 80–90, Kalinin: Kalinin State University. (Scholar)
  • Chandra, A., and Stockmeyer, L., 1976, “Alternation,” in 17th Annual Symposium on Foundations of Computer Science, 1976, pp. 98–108. (Scholar)
  • Chazelle, B., and Monier, L., 1983, “Unbounded hardware is equivalent to deterministic Turing machines,” Theoretical Computer Science, 24(2): 123–130. (Scholar)
  • Cherniak, C., 1981, “Feasible Inferences,” Philosophy of Science, 48: 248–268. (Scholar)
  • –––, 1984, “Computational Complexity and the Universal Acceptance of Logic,” The Journal of Philosophy, 81(12): 739–758. (Scholar)
  • –––, 1986, Minimal Rationality, Cambridge, Massachusetts: MIT Press. (Scholar)
  • Chernoff, H., 1981, “A Note on an Inequality Involving the Normal Distribution,” The Annals of Probability, 9: 533–535. (Scholar)
  • Cherubin, R., and Mannucci, M., 2011, “A Very Short History of Ultrafinitism,” in Juliette Kennedy & Roman Kossak (eds.), Set Theory, Arithmetic, and Foundations of Mathematics: Theorems, Philosophies, Vol. 36, pp. 180–199, Cambridge, England: Cambridge University Press. (Scholar)
  • Church, A., 1936a, “A note on the Entscheidungsproblem,” The Journal of Symbolic Logic, 1(01): 40–41. (Scholar)
  • –––, 1936b, “An unsolvable problem of elementary number theory,” American Journal of Mathematics, 58(2): 345–363. (Scholar)
  • Clarke, E., Emerson, E., and Sistla, A., 1986, “Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications,” ACM Transactions on Programming Languages and Systems, 8(2): 244–263. (Scholar)
  • Cobham, A., 1965, “The Intrinsic Computational Difficulty of Functions,“ Proceedings of the Third International Congress for Logic, Methodology and Philosophy of Science, Amsterdam, North-Holland. (Scholar)
  • Cook, S., 1971, “The complexity of theorem-proving procedures,” Proceedings of the Third Annual ACM Symposium on Theory of Computing, ACM. (Scholar)
  • –––, 1973, “A hierarchy for nondeterministic time complexity,“ Journal of Computer System Science, 7(4):343–353.
  • –––, 2006, “The P versus NP problem,” in J. Carlson, A. Jaffe, & A. Wiles (eds.), The Millennium Prize Problem, pp. 88–104, Providence: American Mathematical Society.
  • Cook, S., and Kolokolova, A., 2001, “A second-order system for polytime reasoning using Gradel’s theorem,” in Logic in Computer Science, 2001. Proceedings. 16th Annual IEEE Symposium on, pp. 177–186. (Scholar)
  • Cook, S., and Mitchell, D., 1997, “Finding Hard Instances of the Satisfiability Problem,” in Satisfiability Problem: Theory and Applications: DIMACS Workshop, March 11-13, 1996, Vol. 35, pp. 1–17, American Mathematical Soc. (Scholar)
  • Cook, S., and Nguyen, P., 2010, Logical foundations of proof complexity, Cambridge, England: Cambridge University Press. (Scholar)
  • Cook, S., and Reckhow, R., 1973, “Time bounded random access machines,” Journal of Computer and System Sciences, 7(4): 354–375. (Scholar)
  • –––, 1979, “The Relative Efficiency of Propositional Proof Systems,” The Journal of Symbolic Logic, 44(01): 36–50. (Scholar)
  • Cook, W., 2012, In pursuit of the Traveling Salesman: mathematics at the limits of computation, Princeton: Princeton University Press. (Scholar)
  • Cormen, T., Leiserson, C., and Rivest, R., 2005, Introduction to Algorithms (Second Ed.), Cambridge, Massachusetts: MIT Press. (Scholar)
  • Crandall, R., and Pomerance, C., 2005, Prime Numbers (Second Ed.), Berlin: Springer. (Scholar)
  • Davis, Martin, and Putnam, Hilary, 1960, “A Computing Procedure for Quantification Theory,” Journal of the ACM (JACM), 7(3): 201–215. (Scholar)
  • DeMillo, R., and Lipton, R., 1980, “The consistency of \(\textbf{P}= \textbf{NP}\) and related problems with fragments of number theory,” in Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pp. 45–57, ACM. (Scholar)
  • Deutsch, D., 1985, “Quantum theory, the Church-Turing principle and the universal quantum computer,” Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818): 97–117. (Scholar)
  • Du, D., and Ko, K., 2000, Theory of Computational Complexity, New York: John Wiley. (Scholar)
  • Dummett, M., 1975, “Wang’s Paradox,” Synthese, 30(3/4): 301–324. (Scholar)
  • Ebbinghaus, Heinz-Dieter, and Flum, Jörg, 1999, Finite Model Theory (Second Ed.), Berlin: Springer. (Scholar)
  • Edmonds, J., 1965a, “Minimum Partition of a Matroid into Independent Subsets,” Journal of Research of the National Bureau of Standards-B. Mathematics and Mathematical Physics, 69: 67–72. (Scholar)
  • –––, 1965b, “Paths, trees, and flowers,” Canadian Journal of Mathematics, 17(3): 449–467. (Scholar)
  • Emde Boas, P. van, 1990, “Machine models and simulations,” in J. Van Leeuwen (ed.), Handbook of theoretical computer science (vol. A): algorithms and complexity, pp. 1–66, Cambridge, Massachusetts: MIT Press. (Scholar)
  • Emerson, E., and Jutla, C., 1988, “The Complexity of Tree Automata and Logics of Programs,” in 29th Annual Symposium on Foundations of Computer Science, 1988., pp. 328–337. (Scholar)
  • Fagin, R., 1974, “Generalized First-Order Spectra and Polynomial-Time Recognizable Sets,” in R. Karp (ed.), Complexity of Computation: SIAM-AMS Proceedings, Vol. 7, pp. 27–41. (Scholar)
  • Fagin, R., and Halpern, J., 1988, “Belief, Awareness, and Limited Reasoning,” Artificial Intelligence, 34(1): 39–76. (Scholar)
  • Fagin, R., Halpern, J., Moses, Y., and Vardi, M., 1995, Reasoning About Knowledge, Cambridge, Massachusetts: MIT Press. (Scholar)
  • Feynman, R., 1982, “Simulating Physics with Computers,” International Journal of Theoretical Physics, 21(6): 467–488. (Scholar)
  • Fischer, M., and Ladner, R., 1979, “Propositional Dynamic Logic of Regular Programs,” Journal of Computer and System Sciences, 18(2): 194–211. (Scholar)
  • Fischer, M., and Rabin, M., 1974, “Super-exponential complexity of Presburger arithmetic,” in R.M. Karp (ed.), Complexity of Computation, Vols. SIAM-AMS Symposium in Applied Mathematics, pp. 122–135. (Scholar)
  • Fortnow, L., 2003, “One Complexity Theorist’s View of Quantum Computing,” Theoretical Computer Science, 292(3): 597–610. (Scholar)
  • –––, 2009, “The status of the P versus NP problem,” Communications of the ACM, 52(9): 78–86. (Scholar)
  • –––, 2013, Golden Ticket: P, NP, and the Search for the Impossible, Princeton: Princeton University Press. (Scholar)
  • Fortnow, L., and Homer, S., 2003, “A short history of computational complexity,” Bulletin of the EATCS, 80: 95–133.
  • Fraenkel, A., and Lichtenstein, D., 1981, “Computing a perfect strategy for \(n \times n\) chess requires time exponential in \(n\),” Journal of Combinatorial Theory, Series A, 31(2): 199–214. (Scholar)
  • Gaifman, H., 2010, “Vagueness, tolerance and contextual logic,” Synthese, 174: 1–42. (Scholar)
  • Gaifman, Haim, 2012, “On Ontology and Realism in Mathematics,” Review of Symbolic Logic, 5(3): 480–512. (Scholar)
  • Gandy, R., 1980, “Church’s Thesis and principles for mechanisms,” in H.J. Keisler J. Barwise & K. Kunen (eds.), The Kleene Symposium, Vol. 101, pp. 123–148, Amsterdam: North-Holland. (Scholar)
  • Ganea, M., 2014, “Finitistic Arithmetic and Classical Logic,” Philosophia Mathematica, 22: 167–197. (Scholar)
  • Garey, M., and Johnson, D., 1979, Computers and intractability. A guide to the theory of NP-completeness, New York: W.H. Freeman; Company. (Scholar)
  • Gigerenzer, G., and Selten, R., 2002, Bounded Rationality: The Adaptive Toolbox, Cambridge, Massachusetts: MIT Press. (Scholar)
  • Goldreich, O., 2010, P, NP, and NP-completeness: The basics of computational complexity, Cambridge, England: Cambridge University Press. (Scholar)
  • Gödel, K., 1932, “Ein Spezialfall des Entscheidungsproblems der theoretischen Logik,” Ergebnisse Eines Mathematischen Kolloquiums, 2: 27–28. (Scholar)
  • –––, 1986a, “On Intuitionistic Arithmetic and Number Theory,” in S. Feferman (ed.), Collected Works Volume 1, pp. 287–295, New York: Oxford University Press. (Scholar)
  • –––, 1986b, “On undecidable propositions of formal mathematical systems (with postscript dated 1964),” in S. Feferman (ed.), Kurt Gödel Collected Works. Vol. I. Publications 1929-1936, pp. 346–371, New York: Oxford University Press. (Scholar)
  • Gödel, Kurt, 1956, “Letter to von Neumann (1956),” Reprinted in Sipser 1992, p. 612. (Scholar)
  • Greenlaw, R., Hoover, H., and Ruzzo, W., 1995, Limits to parallel computation: P-completeness theory, New York: Oxford University Press, USA. (Scholar)
  • Grover, L., 1996, “A Fast Quantum Mechanical Algorithm for Database Search,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212–219, ACM. (Scholar)
  • Gutin, G., and Punnen, A., 2002, The Traveling Salesman Problem and Its Variations Vol. 12, New York: Kluwer. (Scholar)
  • Haken, A., 1985, “The Intractability of Resolution,” Theoretical Computer Science, 39: 297–308. (Scholar)
  • Halpern, J., and Moses, Y., 1992, “A Guide to Completeness and Complexity for Modal Logics of Knowledge and Belief,” Artificial Intelligence, 54(3): 319–379. (Scholar)
  • Harel, D., 2006, Algorithmics: The Spirit of Computing, Boston: Addison-Wesley. (Scholar)
  • Harman, G., 1986, Change in View: Principles of Reasoning., Cambridge, Massachusetts: Cambridge University Press. (Scholar)
  • Hartmanis, J., 1993, “Gödel, von Neumann and the \(\textbf{P}= \textbf{NP}\)? Problem,” in G., Rozenberg, & A. Salomaa (eds.), Current Trends in Theoretical Computer Science, pp. 445–450, Singapore: World Scientific. (Scholar)
  • Hartmanis, J., and Stearns, R., 1965, “On the computational complexity of algorithms,” Transactions of the American Mathematical Society, 117(5): 285–306. (Scholar)
  • Hájek, P., and Pudlák, P., 1998, Metamathematics of First-Order Arithmetic, Berlin: Springer. (Scholar)
  • Hemaspaandra, L., and Ogihara, M., 2002, The Complexity Theory Companion, Berlin: Springer Verlag. (Scholar)
  • Hintikka, J., 1962, Knowledge and Belief: An Introduction to the Logic of the Two Notions, Ithaca: Cornell University Press. (Scholar)
  • Homer, S., and Selman, A., 2011, Turing and the Development of Computational Complexity (No. 2011-06), SUNY Buffalo Department of Computer Science. (Scholar)
  • Hopcroft, J., and Ulman, J., 1979, Introduction to Automata Theory, Languages and Computation, Reading, Massachusetts: Addison-Wesley. (Scholar)
  • Immerman, N., 1982, “Relational Queries Computable in Polynomial Time,” in Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 147–152, ACM. (Scholar)
  • –––, 1987, “Languages That Capture Complexity Classes,” SIAM Journal on Computing, 16(4): 760–778. (Scholar)
  • –––, 1999, Descriptive Complexity, New York: Springer Verlag. (Scholar)
  • Impagliazzo, R., 1995, “A personal view of average-case complexity,” in Structure in Complexity Theory, Proceedings of Tenth Annual IEEE Conference, pp. 134–147.
  • Impagliazzo, R., and Paturi, R., 1999, “Complexity of \(k\)-SAT,” in Computational Complexity, 1999. Proceedings. Fourteenth Annual IEEE Conference, pp. 237–240. (Scholar)
  • Isles, D., 1992, “What evidence is there that \(2^{65536 }\) is a natural number?” Notre Dame Journal of Formal Logic, 33(4). (Scholar)
  • Iwan, S., 2000, “On the Untenability of Nelson’s Predicativism,” Erkenntnis, 53(1-2): 147–154. (Scholar)
  • Kahneman, D., 2003, “A Perspective on Judgment and Choice: Mapping Bounded Rationality.” American Psychologist, 58(9): 697–720. (Scholar)
  • Kanovich, M., 1994, “The complexity of Horn fragments of linear logic,” Annals of Pure and Applied Logic, 69(2): 195–241. (Scholar)
  • Kapovich, I., Myasnikov, A., Schupp, P., and Shpilrain, V., 2003, “Generic-Case Complexity, Decision Problems in Group Theory, and Random Walks,” Journal of Algebra, 264(2): 665–694. (Scholar)
  • Karp, R., 1972, “Reducibility Among Combinatorial Problems,” in R.E. Miller & J.W. Thatcher (eds.), Complexity of computer computations, pp. 85–103, New York: Plenum Press. (Scholar)
  • Kaye, R., 2000, “Minesweeper is NP-complete,” The Mathematical Intelligencer, 22(2): 9–15. (Scholar)
  • Kent, C., and Hodgson, B., 1982, “An arithmetical characterization of NP,” Theoretical Computer Science, 21(3): 255–267. (Scholar)
  • Kleene, S., 1936, “General recursive functions of natural numbers,” Mathematische Annalen, 112(1): 727–742. (Scholar)
  • –––, 1951, Representation of Events in Nerve Nets and Finite Automata (No. RM-704), RAND Corporation. (Scholar)
  • –––, 1952, Introduction to Metamathematics Vol. 1, Amsterdam: North-Holland. (Scholar)
  • Knuth, D., 1973, The Art of Computer Programming Vols. I–III, Reading, Massachusetts: Addison Wesley. (Scholar)
  • Kozen, D., and Parikh, R., 1981, “An elementary proof of the completeness of PDL,” Theoretical Computer Science, 14(1): 113–118. (Scholar)
  • Kuznets, R., 2000, “On the Complexity of Explicit Modal Logics,” in Computer Science Logic, pp. 371–383, Springer. (Scholar)
  • Ladner, R., 1975, “On the Structure of Polynomial Time Reducibility,” Journal of the ACM, 22(1): 155–171. (Scholar)
  • –––, 1977, “The Computational Complexity of Provability in Systems of Modal Propositional Logic,” SIAM Journal on Computing, 6(3): 467–480. (Scholar)
  • Lange, M., 2006, “Model Checking Propositional Dynamic Logic with All Extras,” Journal of Applied Logic, 4(1): 39–49. (Scholar)
  • Lautemann, C., 1983, “BPP and the polynomial hierarchy,” Information Processing Letters, 17(4): 215–217.
  • Leivant, D., 1994, “A Foundational Delineation of Poly-Time,” Information and Computation, 110(2): 391–420. (Scholar)
  • Lenzen, W., 1978, “Recent Work in Epistemic Logic,” Acta Philosophica Fennica, 30: 1–219. (Scholar)
  • Levesque, H., 1984, “A Logic of Implicit and Explicit Belief,” in Proceedings of the Fourth National Conference on Artificial Intelligence (AAAI-84), pp. 198–202. (Scholar)
  • Levin, L., 1973, “Universal sorting problems (Corrected Translation Published in Trakhtenbrot 1984),” Problems of Information Transmission, 9(3): 265–266. (Scholar)
  • Lewis, H., 1980, “Complexity Results for Classes of Quantificational Formulas,” Journal of Computer and System Sciences, 21(3): 317–353. (Scholar)
  • Lewis, H., and Papadimitriou, C., 1998, Elements of the Theory of Computation, Upper Saddle River, New Jersey: Prentice Hall. (Scholar)
  • Li, M., and Vitányi, P., 1997, An Introduction to Kolmogorov Complexity and Its Applications (Second Ed.), New York: Springer. (Scholar)
  • Lichtenstein, D., and Sipser, M., 1980, “Go is polynomial-space hard,” Journal of the ACM, 27(2): 393–401. (Scholar)
  • Lincoln, P., 1995, “Deciding Provability of Linear Logic Formulas,” in Proceedings of the Workshop on Advances in Linear Logic, pp. 109–122, New York: Cambridge University Press. (Scholar)
  • Lincoln, P., Mitchell, J., Scedrov, A., and Shankar, N., 1992, “Decision Problems for Propositional Linear Logic,” Annals of Pure and Applied Logic, 56(1): 239–311. (Scholar)
  • Lipton, R., and Regan, K., 2013, People, Problems, and Proofs, Berlin: Springer. (Scholar)
  • Löwenheim, L., 1967, “On Possibilities in the Calculus of Relatives (1915),” in van Heijenoort (ed.), From Frege to Gödel : A Source Book in Mathematical Logic, 1879-1931, pp. 232–251, Cambridge, Massachusetts: Harvard University Press. (Scholar)
  • Magidor, O., 2011, “Strict Finitism and the Happy Sorites,” Journal of Philosophical Logic, 41: 1–21. (Scholar)
  • Manders, K. L., and Adleman, L., 1978, “NP-complete decision problems for binary quadratics,” Journal of Computer and System Sciences, 16(2): 168–184.
  • Manin, Y., 1980, Computable and Uncomputable, Moscow: Sovetskoye Radio. (Scholar)
  • Marx, M., 2007, “Complexity of Modal Logic,” in P. Blackburn, J. van Benthem, & F. Wolter (eds.), Handbook of Modal Logic, pp. 140–179, Amsterdam: Elsevier. (Scholar)
  • Mermin, N., 2007, Quantum Computer Science: An Introduction, Cambridge, England: Cambridge University Press. (Scholar)
  • Miller, G., 1976, “Riemann’s Hypothesis and Tests for Primality,” Journal of Computer and System Sciences, 13(3): 300–317. (Scholar)
  • Milnikel, R., 2007, “Derivability in certain subsystems of the Logic of Proofs is \(\Pi^P_2\)-complete,” Annals of Pure and Applied Logic, 145(3): 223–239. (Scholar)
  • Moore, C., and Mertens, S., 2011, The Nature of Computation, Oxford: Oxford University Press. (Scholar)
  • Morton, A., 2004, “Epistemic Virtues, Metavirtues, and Computational Complexity,” Noûs, 38(3): 481–502. (Scholar)
  • –––, 2012, Bounded Thinking: Intellectual Virtues for Limited Agents, Oxford: Oxford University Press. (Scholar)
  • Moschovakis, Y., 1974, Elementary Induction on Abstract Structures, Amsterdam: North Holland. (Scholar)
  • Mulmuley, K., and Sohoni, M., 2001, “Geometric complexity theory I: An approach to \(\textbf{P}\) vs. \(\textbf{NP}\) and related problems,” SIAM Journal on Computing, 31(2): 496–526. (Scholar)
  • Mundhenk, M., and Weiß, F., 2010, “The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions,” in A. Kučera & I. Potapov (eds.), Reachability Problems, Vol. 6227, pp. 146–160, Berlin; Heidelberg: Springer. (Scholar)
  • Negri, S., and Von Plato, J., 2001, Structural Proof Theory, Cambridge, England: Cambridge University Press. (Scholar)
  • Nelson, E., 1986, Predicative Arithmetic Vol. 32, Princeton: Princeton University Press. (Scholar)
  • Nielsen, M. A., and Chuang, I., 2000, Quantum Computation and Quantum Information, Cambridge, England: Cambridge University Press. (Scholar)
  • Odifreddi, P., 1999, Classical Recursion Theory. Vol. II Vol. 143, Amsterdam: North-Holland. (Scholar)
  • Papadimitriou, C., 1994, Computational Complexity, New York: Addison-Wesley. (Scholar)
  • Parikh, R., 1971, “Existence and Feasibility in Arithmetic,” Journal of Symbolic Logic, 36(3): 494–508. (Scholar)
  • Pippenger, N., 1979, “On Simultaneous Resource Bounds,” in Foundations of Computer Science, 1979., 20th Annual Symposium on, pp. 307–311, IEEE. (Scholar)
  • Post, E., 1947, “Recursive unsolvability of a problem of Thue,” Journal of Symbolic Logic, 12(1): 1–11. (Scholar)
  • Pudlák, Pavel, 2013, Logical Foundations of Mathematics and Computational Complexity: A Gentle Introduction, Berlin: Springer. (Scholar)
  • Rabin, M., 1980, “Probabilistic Algorithm for Testing Primality,” Journal of Number Theory, 12(1): 128–138. (Scholar)
  • Rabin, M., and Scott, D., 1959, “Finite Automata and Their Decision Problems,” IBM Journal of Research and Development, 3(2): 114–125. (Scholar)
  • Rantala, V., 1982, “Impossible Worlds Semantics and Logical Omniscience,” Acta Philosophica Fennica, 35: 106–115. (Scholar)
  • Razborov, A., and Rudich, S., 1994, “Natural Proofs,” in Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pp. 204–213, ACM. (Scholar)
  • Rivest, R., Shamir, A., and Adleman, L., 1978, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, 21(2): 120–126. (Scholar)
  • Robson, J., 1983, “The complexity of Go,” Information Processing: Proceedings of IFIP Congress, (Scholar)
  • –––, 1984, “\(N\) by \(N\) checkers is EXPTIME complete,” SIAM Journal on Computing, 13(2): 252–267.
  • Rogers, H., 1987, Theory of Recursive Functions and Effective Computability (Second Ed.), Cambridge, Massachusetts: MIT Press. (Scholar)
  • Rose, H., 1984, Subrecursion: functions and hierarchies, Oxford: Clarendon Press. (Scholar)
  • Rubinstein, A., 1998, Modeling Bounded Rationality Vol. 1, Cambridge, Massachusetts: MIT press. (Scholar)
  • Savitch, W., 1970, “Relationship Between Deterministic and Non-Deterministic Tape Classes,” Journal Computer System Science, 4: 177–192. (Scholar)
  • Sazonov, V., 1995, “On Feasible Numbers,” in D. Leivant (ed.), Logic and Computational Complexity, Vol. 960, pp. 30–51, Berlin: Springer. (Scholar)
  • Schorr, A., 1983, “Physical Parallel Devices Are Not Much Faster Than Sequential Ones,” Information Processing Letters, 17(2): 103–106. (Scholar)
  • Schrijver, A., 2005, “On the history of combinatorial optimization (till 1960),” Discrete Optimization, 12: 1–68. (Scholar)
  • Scott, A., and Sorkin, G., 2006, “Solving sparse random instances of MAX CUT and MSC 2-CSP in linear expected time,” Combinatorics, Probability and Computing, 15(1-2): 281–315. (Scholar)
  • Segerlind, N., 2007, “The Complexity of Propositional Proofs,” Bulletin of Symbolic Logic, 13(4): 417–481. (Scholar)
  • Seiferas, J., Fischer, M., and Meyer, A., 1973, “Refinements of the Nondeterministic Time and Space Hierarchies,” in 14th Annual Symposium on Switching and Automata Theory, 1973, pp. 130–137. (Scholar)
  • Shor, P., 1999, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Review, 41(2): pp. 303–332. (Scholar)
  • Sieg, W., 2009, “On Computability,” in Andrew Irvine (ed.), Philosophy of Mathematics, Vol. 4, pp. 549–630, Amsterdam: North-Holland. (Scholar)
  • Simon, H., 1957, Models of Man: Social and Rational, New York: John Wiley. (Scholar)
  • –––, 1972, “Theories of Bounded Rationality,” Decision and Organization, 1: 161–176. (Scholar)
  • Sipser, H., 2006, Introduction to the Theory of Computation, Boston: Thomson. (Scholar)
  • Sipser, M., 1992, “The history and status of the P versus NP question,” in Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 603–618, ACM. (Scholar)
  • Sistla, A., and Clarke, E., 1985, “The Complexity of Propositional Linear Temporal Logics,” Journal of the ACM, 32(3): 733–749. (Scholar)
  • Skolem, T., 1956, “An ordered set of arithmetic functions representing the least \(\epsilon\)-number,” Det Konigelige Norske Videnskabers Selskab Fordhandlinger, 29: 54–59. (Scholar)
  • Slot, C., and Emde Boas, P. van, 1988, “The Problem of Space Invariance for Sequential Machines,” Information and Computation, 77(2): 93–122. (Scholar)
  • Stalnaker, R., 1991, “The problem of logical omniscience, I,” Synthese, 89(3): 425–440. (Scholar)
  • –––, 1999, “The Problem of Logical Omniscience, II,” in Context and Content, pp. 255–283, Oxford: Oxford University Press. (Scholar)
  • Statman, R., 1979, “Intuitionistic Propositional Logic Is Polynomial-Space Complete,” Theoretical Computer Science, 9(1): 67–72. (Scholar)
  • Stearns, R., Hartmanis, J., and Lewis, P., 1965, “Hierarchies of memory limited computations,” in Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pp. 179–190. (Scholar)
  • Stockmeyer, L., 1977, “The Polynomial-Time Hierarchy,” Theoretical Computer Science, 3(1): 1–22. (Scholar)
  • Stockmeyer, L., and Meyer, A., 1973, “Word Problems Requiring Exponential Time (Preliminary Report),” in Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, pp. 1–9, ACM. (Scholar)
  • Trakhtenbrot, B., 1984, “A survey of Russian approaches to perebor (brute-force searches) algorithms,” Annals of the History of Computing, 6(4): 384–400. (Scholar)
  • Troelstra, A., and Schwichtenberg, H., 2000, Basic Proof Theory 2nd ed., Cambridge, England: Cambridge University Press. (Scholar)
  • Turing, A., 1937, “On computable numbers, with an application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 2(1): 230. (Scholar)
  • Tversky, A., and Kahneman, D., 1974, “Judgment Under Uncertainty: Heuristics and Biases,” Science, 185(4157): 1124–1131. (Scholar)
  • Urquhart, A., 1984, “The Undecidability of Entailment and Relevant Implication,” The Journal of Symbolic Logic, 49(4): pp. 1059–1073. (Scholar)
  • Van Bendegem, J., 2012, “A Defense of Strict Finitism,” Constructivist Foundations, 7(2): 141–149. (Scholar)
  • Van Dantzig, D., 1955, “Is \(10^{10^{10}}\) a finite number?Dialectica, 9(3-4): 273–277. (Scholar)
  • Van Den Dries, L., and Levitz, H., 1984, “On Skolem’s exponential functions below \(2^{2^x}\),” Transactions of the American Mathematical Society, 286(1): 339–349. (Scholar)
  • Van Leeuwen, J., 1990, Handbook of theoretical computer science Vol. A, Amsterdam: Elsevier. (Scholar)
  • Vardi, M., 1982, “The Complexity of Relational Query Languages,” in Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 137–146. (Scholar)
  • Vardi, M., and Stockmeyer, L., 1985, “Improved Upper and Lower Bounds for Modal Logics of Programs,” in Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 240–251. (Scholar)
  • Visser, Albert, 2009, “The predicative Frege hierarchy,” Annals of Pure and Applied Logic, 160(2): 129–153. (Scholar)
  • Vitányi, P., 1986, “Nonsequential Computation and Laws of Nature,” in F. Makedon, K. Mehlhorn, T. Papatheodorou, & P. Spirakis (eds.), VLSI Algorithms and Architectures, Vol. 227, pp. 108–120, Berlin; Heidelberg: Springer. (Scholar)
  • Vollmer, H., 1999, Introduction to Circuit Complexity: A Uniform Approach, New York: Springer-Verlag. (Scholar)
  • Vopěnka, P., 1979, Mathematics in the Alternative Set Theory, Leipzig: Teubner. (Scholar)
  • Wagner, K., and Wechsung, G., 1986, Computational Complexity, Dordrecht: Reidel. (Scholar)
  • Wang, H., 1958, “Eighty years of foundational studies,” Dialectica, 12: 466–497. (Scholar)
  • Watrous, J., 2009, “Quantum Computational Complexity,” in Encyclopedia of Complexity and Systems Science, pp. 7174–7201, Berlin: Springer. (Scholar)
  • –––, 2006b, “P, NP and mathematics–a computational complexity perspective,” in Proceedings of the 2006 International Congress of Mathematicians, pp. 665–712.
  • Williams, H., 1998, Édouard Lucas and Primality Testing, New York: Wiley. (Scholar)
  • Wolper, P., 1986, “Expressing Interesting Properties of Programs in Propositional Temporal Logic,” in Proceedings of the 13th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pp. 184–193. (Scholar)
  • Wrathall, C., 1978, “Rudimentary Predicates and Relative Computation,” SIAM Journal on Computing, 7(2): 194–209. (Scholar)
  • Yanofsky, N., and Mannucci, M., 2007, Quantum Computing for Computer Scientists, Cambridge, England: Cambridge University Press. (Scholar)
  • Yessenin-Volpin, A., 1961, “Le Programme Ultra-Intuitionniste Des Fondements Des Mathématiques.” in Infinitistic Methods, Proceedings of the Symposium on the Foundations of Mathematics, pp. 201–223, Oxford: Pergamon Press. (Scholar)
  • –––, 1970, “The Ultra-Intuitionistic Criticism and the Antitraditional Program for the Foundations of Mathematics,” in A. Kino, J. Myhill, & R. Vesley (eds.), Intuitionism and Proof Theory, pp. 3–45, Amsterdam: North-Holland. (Scholar)
  • Yablonski, S. 1959, “On the impossibility of eliminating perebor in solving some problems of circuit theory,” Dokl. A.N. SSSR 124: 44–47 (Scholar)
  • Zambella, D., 1996, “Notes on Polynomially Bounded Arithmetic,” The Journal of Symbolic Logic, 61(3): 942–966. (Scholar)

Generated Sun Nov 22 09:05:21 2020