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 complexity class P describes the class of feasibly de... — Carmelics
    Home/Truth & Knowledge
    HistoryEditSee Inverse

    The complexity class P describes the class of feasibly decidable problems

    Proof of definition segments
    ?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 Cobham-Edmonds Thesis identifies feasible decidability with polynomial-time decidability
      ?

      Think about whether this reason is strong or weak

    • 2.The class P is defined relative to the deterministic Turing machine model, which is assumed to be a reasonable model of computation
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Problems solvable in O(n^1000000) time are technically in P but are computationally infeasible for any realistic input size.
      ?

      Think about whether this reason is strong or weak

    • 2.The Cobham-Edmonds Thesis conflates mathematical tractability with physical feasibility by ignoring the magnitude of polynomial constants and exponents.
      ?

      Think about whether this reason is strong or weak

    • 3.Feasibility is an empirical and resource-relative notion that cannot be captured by any single complexity class defined purely by asymptotic growth.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The identification of P with feasibility is model-dependent, yet Turing machines do not accurately represent the parallel or quantum computational architectures available in practice.
      ?

      Think about whether this reason is strong or weak

    • 2.Parberry (1986) and others have argued that the Church-Turing Thesis does not entail that polynomial time on a Turing machine tracks feasibility across all physically realizable computation models.
      ?

      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 & KnowledgeProof of definition segments

    Related

    Feasibility is an empirical and resource-relative notion that cannot be captured...Parberry (1986) and others have argued that the Church-Turing Thesis does not en...Problems solvable in O(n^1000000) time are technically in P but are computationa...The Cobham-Edmonds Thesis conflates mathematical tractability with physical feas...
    +3 moreShow less
    The Cobham-Edmonds Thesis identifies feasible decidability with polynomial-time ...The class P is defined relative to the deterministic Turing machine model, which...The identification of P with feasibility is model-dependent, yet Turing machines...

    Similar

    P is the class of problems decidable efficiently89%P is the class of problems decidable efficiently.89%PSPACE is a complexity class between PH and EXP86%The class F provides a machine-independent characterization of the com...84%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    1 Deterministic and non-deterministic models of computation According to the Cobham-Edmonds Thesis the complexity class \(\textbf{P}\) describes the class of feasibily decidable problems. As we have just seen, this class is defined in terms of the reference model \(\mathfrak{T}\) in virtue of the assumption that it is a ‘reasonable’ model of computation. Several other models of computation are also studied in complexity theory not because they are presumed to be accurate representations of the c
    Extraction notes

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

    Details

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