Philosophy of Science 82 (5):941-955 (2015)

Sorin Bangu
University of Bergen
Modern mathematical sciences are hard to imagine without appeal to efficient computational algorithms. We address several conceptual problems arising from this interaction by outlining rival but complementary perspectives on mathematical tractability. More specifically, we articulate three alternative characterizations of the complexity hierarchy of mathematical problems that are themselves based on different understandings of computational constraints. These distinctions resolve the tension between epistemic contexts in which exact solutions can be found and the ones in which they cannot; however, contrary to a persistent myth, we conclude that having an exact solution is not generally more epistemologically beneficial than lacking one.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1086/683343
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,257
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Computing Machinery and Intelligence.Alan M. Turing - 1950 - Mind 59 (October):433-60.

Add more references

Citations of this work BETA

On the Presumed Superiority of Analytical Solutions Over Numerical Methods.Vincent Ardourel & Julie Jebeile - 2017 - European Journal for Philosophy of Science 7 (2):201-220.
Conceptual and Computational Mathematics†.Nicolas Fillion - 2019 - Philosophia Mathematica 27 (2):199-218.
Semantic layering and the success of mathematical sciences.Nicolas Fillion - 2021 - European Journal for Philosophy of Science 11 (3):1-25.
Numerical Instability and Dynamical Systems.Vincent Ardourel & Julie Jebeile - 2021 - European Journal for Philosophy of Science 11 (2):1-21.

View all 6 citations / Add more citations

Similar books and articles

Computation Models for Parameterized Complexity.Marco Cesati & Miriam Dilanni - 1997 - Mathematical Logic Quarterly 43 (2):179-202.
Computability, Complexity, Logic.Egon Börger - 1989 - New York: U.S.A.Elsevier Science Pub. Co..
Abstract Complexity Theory and the Δ20 Degrees.Benjamin Schaeffer - 2002 - Annals of Pure and Applied Logic 115 (1-3):195-231.
Complexity-Based Theories of Emergence: Criticisms and Constraints.Kari L. Theurer - 2014 - International Studies in the Philosophy of Science 28 (3):277-301.
Computational Complexity on Computable Metric Spaces.Klaus Weirauch - 2003 - Mathematical Logic Quarterly 49 (1):3-21.
Computational Model Theory: An Overview.M. Vardi - 1998 - Logic Journal of the IGPL 6 (4):601-624.
Two Proof-Theoretic Remarks on EA + ECT.Volker Halbach & Leon Horsten - 2000 - Mathematical Logic Quarterly 46 (4):461-466.
Theories of Complexity and Their Problems.Hans Poser - 2007 - Frontiers of Philosophy in China 2 (3):423-436.
Complexity of Admissible Rules.Emil Jeřábek - 2007 - Archive for Mathematical Logic 46 (2):73-92.
Why Philosophers Should Care About Computational Complexity.Scott Aaronson - 2013 - Computability: Turing, Gödel, Church, and Beyond:261--328.


Added to PP index

Total views
30 ( #379,020 of 2,499,868 )

Recent downloads (6 months)
1 ( #417,749 of 2,499,868 )

How can I increase my downloads?


My notes