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
    Cobham and Edmonds' identification of polynomial time wit... — Carmelics
    Home
    HistoryEditSee Inverse

    Part of a larger discussion

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

    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.

    ?Rate how convincing each reason is below to see the overall strength.
    1 reason for
    1 reason against

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.Polynomial time is a mathematical abstraction that fails to capture practical runtime constraints that matter for real computing.
      ?

      Think about whether this reason is strong or weak

    • 2.Empirically, O(n^100) algorithms cannot solve problems of realistic size, making the P class theoretically broad but practically hollow.
      ?

      Think about whether this reason is strong or weak

    • 3.Feasibility requires algorithms whose runtime remains manageable across problem instances engineers actually encounter in practice.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    1 perspective
    Reason against
    ?
    • 1.Cobham-Edmonds thesis correctly identifies a robust complexity class; O(n^100) algorithms are vanishingly rare in practice.
      ?

      Think about whether this reason is strong or weak

    • 2.Without a clear mathematical criterion like polynomial time, 'feasibility' becomes subjective, context-dependent, and non-comparable.
      ?

      Think about whether this reason is strong or weak

    • 3.The threshold between feasible and infeasible must be defined formally; practical engineering concerns are separate from complexity theory.
      ?

      Think about whether this reason is strong or weak

    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.

    Key Terms

    Cobham and Edmonds(as referenced theorists in computational complexity)
    Two computer scientists who proposed that if a problem can be solved in polynomial time, it's realistically solvable by computers in the real world.
    Complexity theorists(as the academic field analyzing these debates)
    Scientists who study how difficult different computational problems are and how fast computers can solve them.
    Feasibility(as used in logic and computation)
    Whether something is actually possible to do in practice, considering real-world limitations like time and resources—not just theoretically possible.
    O(n^100)(as an example of polynomial time that is impractical)
    A mathematical notation meaning an algorithm's time grows as the 100th power of the input size—so doubling the input makes it about a trillion times slower.
    Parberry and Levin(as competing theorists in computational complexity)
    Complexity theorists (computer scientists who study how hard problems are to solve) who disagreed with the Cobham-Edmonds idea.
    polynomial time(Used to characterize feasible computation)
    Computational time complexity expressed as t(x)=x^c, where c is a constant and x is the length of the input

    Connections

    2 topics

    All sources support it1 linkedTruth & Knowledge1 linked

    Related

    Cobham-Edmonds thesis correctly identifies a robust complexity class; O(n^100) a...Empirically, O(n^100) algorithms cannot solve problems of realistic size, making...

    Details

    Type
    claim
    Perspectives
    2 (1 for, 1 against)
    Edits
    1 edit
    Feasibility requires algorithms whose runtime remains manageable across problem ...
    Polynomial time is a mathematical abstraction that fails to capture practical ru...
    +3 moreShow less
    The Computational Efficiency Thesis (CET) is supported by a quasi-inductive argu...The threshold between feasible and infeasible must be defined formally; practica...Without a clear mathematical criterion like polynomial time, 'feasibility' becom...