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
    Possession of a polynomial time decision algorithm is suf... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Truth & Knowledge
    HistoryEditSee Inverse

    Possession of a polynomial time decision algorithm is sufficient grounds for regarding a problem as feasibly decidable.

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

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.The Invariance Thesis implies that whether a problem admits a polynomial time algorithm is independent of which reasonable model of computation is used to measure time complexity.
      ?

      Think about whether this reason is strong or weak

    • 2.Polynomial time algorithms scale in a manner that remains tractable as input size grows, unlike exponential time algorithms.
      ?

      Think about whether this reason is strong or weak

    • 3.Cobham and Edmonds independently proposed this criterion as the positive counterpart to the intractability condition.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.A polynomial algorithm with degree 100 or leading coefficient 10^50 is computationally infeasible on any physically realizable machine.
      ?

      Think about whether this reason is strong or weak

    • 2.Feasibility is an empirical and engineering concept tied to actual resource constraints, not an abstract worst-case asymptotic property.
      ?

      Think about whether this reason is strong or weak

    • 3.Cobham himself acknowledged that the identification of P with feasibility was a theoretical idealization, not a literal claim about practice.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The Invariance Thesis establishes machine-independence of polynomial time only up to polynomial translation, which presupposes the very criterion it is meant to justify.
      ?

      Think about whether this reason is strong or weak

    • 2.Circular justification of a complexity class via a thesis that already encodes polynomial-time equivalence cannot ground the normative claim that P equals feasibility.
      ?

      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.

    Topics

    Truth & KnowledgeAll sources support it

    Connections

    1 linked claim · 2 topics

    Causation1 linkedModality & Possibility1 linked
    Possession of a polynomial time algorithm is sufficient grounds for regarding a ...

    Related

    A polynomial algorithm with degree 100 or leading coefficient 10^50 is computati...Circular justification of a complexity class via a thesis that already encodes p...Cobham and Edmonds independently proposed this criterion as the positive counter...Cobham himself acknowledged that the identification of P with feasibility was a ...
    +5 moreShow less
    Feasibility is an empirical and engineering concept tied to actual resource cons...Polynomial time algorithms scale in a manner that remains tractable as input siz...

    Similar

    Possession of a polynomial time decision algorithm is sufficient groun...98%Possession of a polynomial time algorithm is sufficient grounds for re...96%To apply the Cobham-Edmonds Thesis and judge whether a problem X is fe...86%The Cobham-Edmonds Thesis identifies feasible decidability with polyno...84%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    e. that of effective computability. It is also natural to ask whether the concept of feasible computability described in Section 1 itself admits a mathematical analysis similar to Church’s Thesis. We saw above that \(\sc{FACTORIZATION}\) is an example of a problem of antecedent mathematical and practical interest for which more efficient algorithms have historically been sought. The task of efficiently solving combinatorial problems of the sort exemplified by \(\sc{TSP}\), \(\sc{INTEGER}\
    Extraction notes

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

    Details

    Possession of a polynomial time algorithm is sufficient grounds for regarding a ...
    The Invariance Thesis establishes machine-independence of polynomial time only u...
    The Invariance Thesis implies that whether a problem admits a polynomial time al...
    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit