pith. sign in

arxiv: 2607.00315 · v1 · pith:GB4ZDXAGnew · submitted 2026-07-01 · 💻 cs.CC

Feasibilism, Explication, and the Cobham-Edmonds Thesis

Abrahim Ladha , Yiran Luo , Alan Tian This is my paper

Pith reviewed 2026-07-02 00:45 UTC · model grok-4.3

classification 💻 cs.CC
keywords Cobham-Edmonds thesisChurch-Turing thesisfeasible computationcomplexity class Pexplicationfeasibilism
0
0 comments X

The pith

Arguments that support the Church-Turing thesis can be adapted to support the Cobham-Edmonds thesis that feasible computation is the class P.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops arguments for the Cobham-Edmonds thesis by transferring the structure of well-known arguments for the Church-Turing thesis. The Church-Turing thesis equates effective calculability with Turing-machine decidability while the Cobham-Edmonds thesis equates feasible computation with polynomial-time decidability in the class P. By constructing parallel justifications, the work aims to move beyond claims that P is merely useful and toward the stronger position that P is the correct target of explication for feasibility. A sympathetic reader would care because this supplies a philosophical basis for treating polynomial time as the formal boundary of feasible computation rather than an arbitrary cutoff.

Core claim

The paper claims that many of the arguments developed in favor of the Church-Turing thesis can be presented in analogous form in favor of the Cobham-Edmonds thesis, which asserts that feasible computation explicates to the complexity class P of problems decidable by a polynomial-time bounded Turing machine.

What carries the argument

The analogy that transfers arguments from effective calculability to feasible computation.

Load-bearing premise

Arguments developed for the Church-Turing thesis transfer meaningfully to the Cobham-Edmonds thesis without requiring independent justification for the analogy itself.

What would settle it

A demonstration that at least one major argument used for the Church-Turing thesis has no valid counterpart when applied to the notion of feasibility.

read the original abstract

While the Church-Turing thesis asserts that effective calculability explicates to sets decidable by a Turing machine, the Cobham-Edmonds thesis asserts that feasible computation explicates to the complexity class $\mathsf{P}$, those decidable by a polynomial-time bounded Turing machine. The Church-Turing thesis has been placed under rigorous scrutiny and has several convincing arguments in its favor, but the Cobham-Edmonds thesis has not undergone a similar examination. Many of the arguments in its favor simply suggest that $\mathsf{P}$ is a useful assumption, rather than a necessary target. This paper presents analogous arguments in favor of the Cobham-Edmonds thesis.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper claims that the Cobham-Edmonds thesis (feasible computation explicates to P) can be supported by arguments analogous to those that have been developed for the Church-Turing thesis (effective calculability explicates to Turing-computable functions). It observes that existing defenses of the Cobham-Edmonds thesis typically establish only the usefulness of P rather than its necessity as an explication, and seeks to supply necessity-style arguments via this analogy.

Significance. If the constructed analogies are successful, the work would strengthen the philosophical case for P as the correct formalization of feasibility by supplying necessity-based justifications parallel to those for the Church-Turing thesis. This addresses a recognized gap in the literature on the Cobham-Edmonds thesis and could encourage similar analogical reasoning in other foundational questions in complexity theory.

major comments (1)
  1. [§2] The central move—transferring justificatory force from Church-Turing arguments to the Cobham-Edmonds thesis—rests on an unexamined structural analogy between 'effective calculability' and 'feasible computation.' This assumption is load-bearing for the paper's contribution and requires explicit defense; without it, the analogous arguments do not automatically inherit the same normative weight.
minor comments (1)
  1. A side-by-side comparison (perhaps in a table) of the original Church-Turing arguments and their proposed Cobham-Edmonds counterparts would improve readability and allow readers to evaluate the fidelity of the analogy.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive report and for highlighting the load-bearing role of the structural analogy. We agree that this requires explicit defense and will revise the manuscript to address it directly.

read point-by-point responses

  1. Referee: [§2] The central move—transferring justificatory force from Church-Turing arguments to the Cobham-Edmonds thesis—rests on an unexamined structural analogy between 'effective calculability' and 'feasible computation.' This assumption is load-bearing for the paper's contribution and requires explicit defense; without it, the analogous arguments do not automatically inherit the same normative weight.

    Authors: We accept this criticism. The current manuscript constructs parallel arguments but does not contain a dedicated defense of why the pre-theoretic notions of effective calculability and feasible computation stand in a sufficiently close structural relation to license the transfer of justificatory force. In the revised version we will add a new subsection (likely §2.1) that explicitly articulates the relevant structural parallels—shared closure properties under composition and bounded recursion, the existence of universal machines, and the way both notions are intended to capture informal computational practice—while also addressing potential disanalogies such as the introduction of resource bounds. This addition will make the normative transfer explicit rather than implicit. revision: yes

Circularity Check

0 steps flagged

No circularity; analogical construction is self-contained

full rationale

The paper's project is to supply necessity-style arguments for the Cobham-Edmonds thesis by explicit analogy to existing arguments for the Church-Turing thesis. No equations, fitted parameters, or derivations appear; the central move is philosophical transfer of argumentative structure rather than any reduction of a prediction or uniqueness claim to a self-citation or definitional input. The analogy is presented as the contribution itself and does not rely on load-bearing self-citations or ansatzes that collapse into the target result. The manuscript is therefore self-contained against external benchmarks with no internal circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review provides insufficient detail to enumerate free parameters, axioms, or invented entities with precision.

axioms (1)
  • domain assumption The Church-Turing thesis has several convincing arguments in its favor.
    Stated directly in the abstract as background.

pith-pipeline@v0.9.1-grok · 5642 in / 1044 out tokens · 28557 ms · 2026-07-02T00:45:10.578356+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

112 extracted references · 30 canonical work pages

  1. [1]

    Guest Column: NP-complete problems and physical reality , volume =

    Aaronson, Scott , year =. Guest Column: NP-complete problems and physical reality , volume =. ACM SIGACT News , publisher =. doi:10.1145/1052796.1052804 , number =

    work page doi:10.1145/1052796.1052804

  2. [2]

    Annals of mathematics , publisher =

    Agrawal, Manindra and Kayal, Neeraj and Saxena, Nitin , year =. Annals of mathematics , publisher =

  3. [3]

    2013 , journal =

    Is quantum mechanics falsifiable? A computational perspective on the foundations of quantum mechanics , author =. 2013 , journal =

    2013

  4. [4]

    1936 , journal =

    On Computable Numbers, with an Application to the Entscheidungsproblem , author =. 1936 , journal =

    1936

  5. [5]

    1986 , journal =

    The Complexity of Analog Computation , author =. 1986 , journal =. doi:10.1016/0378-4754(86)90105-9 , issn =

    work page doi:10.1016/0378-4754(86)90105-9 1986

  6. [6]

    ACM Transactions on Computational Logic , publisher =

    A new function algebra of EXPTIME functions by safe nested recursion , author =. ACM Transactions on Computational Logic , publisher =. 2009 , month =. doi:10.1145/1555746.1555748 , issn =

    work page doi:10.1145/1555746.1555748 2009

  7. [7]

    2009 , publisher =

    Computational complexity: a modern approach , author =. 2009 , publisher =

    2009

  8. [8]

    Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , publisher =

    Graph isomorphism in quasipolynomial time [extended abstract] , author =. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , publisher =. 2016 , month =. doi:10.1145/2897518.2897542 , url =

    work page doi:10.1145/2897518.2897542 2016

  9. [9]

    Relativizations of the

    Baker, Theodore and Gill, John and Solovay, Robert , year =. Relativizations of the. SIAM Journal on computing , publisher =

  10. [10]

    1977 , booktitle =

    An introduction to first-order logic , author =. 1977 , booktitle =

    1977

  11. [11]

    1992 , booktitle =

    A new recursion-theoretic characterization of the polytime functions (extended abstract) , author =. 1992 , booktitle =. doi:10.1145/129712.129740 , isbn =

    work page doi:10.1145/129712.129740 1992

  12. [12]

    Relative to a Random Oracle A,

    Bennett, Charles H and Gill, John , year =. Relative to a Random Oracle A,. SIAM Journal on Computing , publisher =

  13. [13]

    1982 , school =

    Hilbert's thesis: some considerations about formalizations of mathematics , author =. 1982 , school =

    1982

  14. [14]

    Sur le platonisme dans les math

    Bernays, Paul , year =. Sur le platonisme dans les math. L’enseignement math

  15. [15]

    1993 , booktitle =

    Quantum complexity theory , author =. 1993 , booktitle =

    1993

  16. [16]

    2017 , journal =

    An argument for p= np , author =. 2017 , journal =

    2017

  17. [17]

    2004 , journal =

    P=NP , author =. 2004 , journal =

    2004

  18. [18]

    1999 , journal =

    Bounded arithmetic, proof complexity and two papers of Parikh , author =. 1999 , journal =

    1999

  19. [19]

    1985 , publisher =

    Bounded arithmetic , author =. 1985 , publisher =

    1985

  20. [20]

    2026 , booktitle =

    A Theory for Probabilistic Polynomial-Time Reasoning , author =. 2026 , booktitle =. doi:10.1145/3798129.3800842 , isbn =

    work page doi:10.1145/3798129.3800842 2026

  21. [21]

    1936 , journal =

    An unsolvable problem of elementary number theory , author =. 1936 , journal =

    1936

  22. [22]

    1965 , booktitle =

    The Intrinsic Computational Difficulty of Functions , author =. 1965 , booktitle =

    1965

  23. [23]

    Cook, Stephen , year =. The. Clay Mathematics Institute , volume =

  24. [24]

    2007 , journal =

    Physical computation: How general are Gandy’s principles for mechanisms? , author =. 2007 , journal =

    2007

  25. [25]

    2016 , school =

    Constructivity and predicativity: Philosophical foundations , author =. 2016 , school =

    2016

  26. [26]

    2021 , journal =

    Explication as a three-step procedure: the case of the Church-Turing thesis , author =. 2021 , journal =

    2021

  27. [27]

    2019 , journal =

    Computational complexity theory and the philosophy of mathematics , author =. 2019 , journal =

    2019

  28. [28]

    2008 , journal =

    A natural axiomatization of computability and proof of Church's Thesis , author =. 2008 , journal =

    2008

  29. [29]

    2011 , publisher =

    Theory of computational complexity , author =. 2011 , publisher =

    2011

  30. [30]

    1975 , journal =

    Wang's paradox , author =. 1975 , journal =

    1975

  31. [31]

    2017 , journal =

    Carnapian Explication, Formalisms as Cognitive Tools, and the Paradox of Adequate Formalization , author =. 2017 , journal =

    2017

  32. [32]

    1965 , journal =

    Paths, trees, and flowers , author =. 1965 , journal =

    1965

  33. [33]

    1976 , journal =

    An efficient implementation of Edmonds' algorithm for maximum matching on graphs , author =. 1976 , journal =

    1976

  34. [34]

    , author =

    On the Unreasonable Effectiveness of SAT Solvers. , author =

  35. [35]

    2021 , url =

    The Argument against Quantum Computers, the Quantum Laws of Nature, and Google's Supremacy Claims , author =. 2021 , url =. 2008.05188 , archiveprefix =

    work page arXiv 2021

  36. [36]

    1974 , booktitle =

    Computational complexity of probabilistic Turing machines , author =. 1974 , booktitle =

    1974

  37. [37]

    1994 , booktitle =

    Light linear logic , author =. 1994 , booktitle =

    1994

  38. [38]

    Computational complexity

    Goldreich, Oded. Computational complexity

  39. [39]

    1991 , journal =

    Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems , author =. 1991 , journal =

    1991

  40. [40]

    2026 , journal =

    Feasible constructivism , author =. 2026 , journal =

    2026

  41. [41]

    1993 , journal =

    Feasible functions , author =. 1993 , journal =

    1993

  42. [42]

    1990 , journal =

    Knowledge and common knowledge in a distributed environment , author =. 1990 , journal =

    1990

  43. [43]

    1975 , journal =

    From Mathematics to Philosophy , author =. 1975 , journal =

    1975

  44. [44]

    1965 , journal =

    On the computational complexity of algorithms , author =. 1965 , journal =

    1965

  45. [45]

    1966 , month = oct, journal =

    Two-Tape Simulation of Multitape Turing Machines , author =. 1966 , month = oct, journal =. doi:10.1145/321356.321362 , issn =

    work page doi:10.1145/321356.321362 1966

  46. [46]

    1965 , journal =

    One-tape, off-line Turing machine computations , author =. 1965 , journal =

    1965

  47. [47]

    2001 , journal =

    Introduction to automata theory, languages, and computation , author =. 2001 , journal =

    2001

  48. [48]

    1999 , journal =

    A pseudorandom generator from any one-way function , author =. 1999 , journal =

    1999

  49. [49]

    1982 , booktitle =

    Relational queries computable in polynomial time , author =. 1982 , booktitle =

    1982

  50. [50]

    Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages =

    Impagliazzo, Russell and Wigderson, Avi , year =. Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages =

  51. [51]

    2007 , journal =

    Approximate counting in bounded arithmetic , author =. 2007 , journal =. doi:10.2178/jsl/1191333850 , issn =

    work page doi:10.2178/jsl/1191333850 2007

  52. [52]

    2020 , booktitle =

    The argument against quantum computers , author =. 2020 , booktitle =

    2020

  53. [53]

    1984 , booktitle =

    A new polynomial-time algorithm for linear programming , author =. 1984 , booktitle =

    1984

  54. [54]

    1980 , journal =

    Polynomial algorithms in linear programming , author =. 1980 , journal =

    1980

  55. [55]

    , year =

    Kleene, Stephen C. , year =. Origins of Recursive Function Theory , volume =. IEEE Annals of the History of Computing , publisher =. doi:10.1109/mahc.1981.10004 , number =

    work page doi:10.1109/mahc.1981.10004 1981

  56. [56]

    1995 , publisher =

    Bounded arithmetic, propositional logic and complexity theory , author =. 1995 , publisher =

    1995

  57. [57]

    , year =

    Kripke, Saul A. , year =. The. Computability: Turing, Gödel, Church, and Beyond , publisher =. doi:10.7551/mitpress/8009.003.0005 , isbn =

    work page doi:10.7551/mitpress/8009.003.0005

  58. [58]

    2003 , journal =

    Polynomial Time and Extravagant Models , author =. 2003 , journal =

    2003

  59. [59]

    1994 , journal =

    A foundational delineation of poly-time , author =. 1994 , journal =

    1994

  60. [60]

    1991 , booktitle =

    A foundational delineation of computational feasibility , author =. 1991 , booktitle =

    1991

  61. [61]

    Mathematische Annalen , publisher =

    Factoring polynomials with rational coefficients , author =. Mathematische Annalen , publisher =. 1982 , month =. doi:10.1007/bf01457454 , issn =

    work page doi:10.1007/bf01457454 1982

  62. [62]

    1982 , publisher =

    Factoring polynomials with rational coefficients , author =. 1982 , publisher =

    1982

  63. [63]

    1998 , journal =

    Elements of the Theory of Computation , author =. 1998 , journal =

    1998

  64. [64]

    2025 , booktitle =

    An introduction to feasible mathematics and bounded arithmetic for computer scientists , author =. 2025 , booktitle =

    2025

  65. [65]

    2008 , publisher =

    An introduction to Kolmogorov complexity and its applications , author =. 2008 , publisher =

    2008

  66. [66]

    2023 , journal =

    Predicativism as a form of potentialism , author =. 2023 , journal =

    2023

  67. [67]

    1943 , journal =

    A logical calculus of the ideas immanent in nervous activity , author =. 1943 , journal =

    1943

  68. [68]

    La premi\`ere m\'ethode g\'en\'erale de factorisation des polyn\^omes

    Mignotte, Maurice and. La premi\`ere m\'ethode g\'en\'erale de factorisation des polyn\^omes. 2001 , journal =. doi:10.24033/rhm.108 , url =

    work page doi:10.24033/rhm.108 2001

  69. [69]

    1975 , booktitle =

    Riemann's hypothesis and tests for primality , author =. 1975 , booktitle =

    1975

  70. [70]

    1995 , journal =

    Paper machines , author =. 1995 , journal =

    1995

  71. [71]

    1995 , booktitle =

    When is an algorithm feasible? Soft computing approach , author =. 1995 , booktitle =

    1995

  72. [72]

    1994 , publisher =

    Computational Complexity , author =. 1994 , publisher =

    1994

  73. [73]

    1971 , journal =

    Existence and feasibility in arithmetic , author =. 1971 , journal =

    1971

  74. [74]

    1918 , journal =

    Science and Method, trans , author =. 1918 , journal =

    1918

  75. [75]

    The Logic of Scientific Discovery , year =

    Karl Popper , editor =. The Logic of Scientific Discovery , year =

  76. [76]

    2021 , journal =

    Can Church's Thesis be Viewed as a Carnapian Explication? , author =. 2021 , journal =

    2021

  77. [77]

    1980 , journal =

    Probabilistic algorithm for testing primality , author =. 1980 , journal =

    1980

  78. [78]

    Natural Proofs , volume =

    Razborov, Alexander A and Rudich, Steven , year =. Natural Proofs , volume =. Journal of Computer and System Sciences , publisher =. doi:10.1006/jcss.1997.1494 , number =

    work page doi:10.1006/jcss.1997.1494 1997

  79. [79]

    2022 , month =

    Juris Hartmanis 1928-2022 , author =. 2022 , month =

    1928

  80. [80]

    1980 , booktitle =

    Church's Thesis and Principles for Mechanisms , author =. 1980 , booktitle =. doi:10.1016/S0049-237X(08)71257-6 , isbn =

    work page doi:10.1016/s0049-237x(08)71257-6 1980

Showing first 80 references.