Skip to content
Carmelics
TopicsThinkersChangesContributorsLoading account…

    Carmelics

    A reasoning platform. Break down any belief into clear reasons, explore both sides, and weigh the evidence honestly.

    Navigate

    • Topics
    • Search
    • Recent Changes
    • Contribute
    • How It Works
    • Glossary
    • Thinkers
    • Contributors
    • About
    • Statistics
    • Terms
    • Privacy

    Database

    Statements
    —
    Perspectives
    —
    Topics
    —

    Press ? for keyboard shortcuts

    LoyalLoyalJusticeJustice
    Made withinDC&Austin
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    The Computational Efficiency Thesis (CET) is supported by... — Carmelics
    Home/Truth & Knowledge
    HistoryEditSee Inverse

    The Computational Efficiency Thesis (CET) is supported by a quasi-inductive argument analogous to the quasi-inductive argument for the Church-Turing Thesis (CT).

    All sources support itTruth & Knowledge
    ?Rate how convincing each reason is below to see the overall strength.
    1 reason for
    2 reasons against

    Sign in or register to share your perspective on this statement.

    Next step

    Based on where you are in your exploration

    Strongest counterpoint
    Explore the most compelling reason on the other side.

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.In cases where we can uniformly compute the values of a function (or decide a problem) for the class of instances we are concerned with in practice, this is typically because a polynomial time algorithm has been discovered that can be implemented on current computing hardware and hence also as a Turing machine.
      ?

      Think about whether this reason is strong or weak

    • 2.In cases where we are currently unable to uniformly compute the values of a function (or decide a problem) for all arguments of interest, it is typically the case that no polynomial time algorithm has been discovered.
      ?

      Think about whether this reason is strong or weak

    • 3.In many cases where no polynomial time algorithm is known, there is also circumstantial evidence that no such algorithm can exist.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The quasi-inductive argument for CT derives force from convergence across distinct computational models (Turing machines, lambda calculus, recursive functions), whereas CET lacks analogous model-independence.
      ?

      Think about whether this reason is strong or weak

    • 2.Polynomial-time tractability is defined relative to a specific machine model; problems tractable on parallel or quantum architectures may remain intractable on Turing machines, undermining the universality CET requires.
      ?

      Think about whether this reason is strong or weak

    • 3.Without cross-model convergence, the inductive evidence for CET is merely historical contingency about which algorithms humans have discovered, not a principled basis for a thesis about computational feasibility.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Cobham and Edmonds' identification of polynomial time with feasibility has been contested by complexity theorists like Parberry and Levin, who note that O(n^100) algorithms are polynomial yet practically infeasible.
      ?

      Think about whether this reason is strong or weak

    • 2.If the extension of 'feasibility' tracked by CET is conceptually unstable or context-dependent, then the inductive evidence for CET fails to converge on a single well-defined thesis in the way CT's evidence converges on computability.
      ?

      Think about whether this reason is strong or weak

    Topics

    Truth & KnowledgeAll sources support it

    Connections

    1 topic

    Skepticism3 linked

    Related

    Cobham and Edmonds' identification of polynomial time with feasibility has been ...If the extension of 'feasibility' tracked by CET is conceptually unstable or con...In cases where we are currently unable to uniformly compute the values of a func...In cases where we can uniformly compute the values of a function (or decide a pr...
    +4 moreShow less
    In many cases where no polynomial time algorithm is known, there is also circums...Polynomial-time tractability is defined relative to a specific machine model; pr...The quasi-inductive argument for CT derives force from convergence across distin...Without cross-model convergence, the inductive evidence for CET is merely histor...

    Similar

    A quasi-inductive argument parallel to that supporting Church's Thesis...93%Hume's argument for the Copy Principle is inductive in form84%Inference to the Best Explanation (IBE) either contradicts itself or e...77%The presupposition of the Uniformity Principle must itself be supporte...77%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    It is also possible to make a case for CET which parallels the quasi-inductive argument for CT. For in cases where we can compute the values of a function (or decide a problem) uniformly for the class of instances we are concerned with in practice, this is typically so precisely because we have discovered a polynomial time algorithm which can be implemented on current computing hardware (and hence also as a Turing machine). And in instances where we are currently unable to uniformly compute the
    Extraction notes

    Validity: Extracted via Max plan + API grounding/validity checks

    Details

    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit