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
    Practical computability correlates with the existence of ... — Carmelics
    Home/Skepticism
    HistoryEditSee Inverse

    Practical computability correlates with the existence of polynomial time algorithms.

    Skepticism
    ?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.In cases where a function can be uniformly computed for practically relevant inputs, a polynomial time algorithm implementable on current hardware has typically been discovered.
      ?

      Think about whether this reason is strong or weak

    • 2.In cases where uniform computation is not currently possible, a polynomial time algorithm has typically not been discovered, and circumstantial evidence often suggests none can exist.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Cobham-Edmonds thesis conflates worst-case complexity with practical performance, ignoring average-case and fixed-parameter tractability.
      ?

      Think about whether this reason is strong or weak

    • 2.Many exponential-time algorithms (e.g., simplex method) perform efficiently in practice, while some polynomial algorithms (e.g., ellipsoid method) are practically useless.
      ?

      Think about whether this reason is strong or weak

    • 3.The correlation between polynomial-time solvability and practical computability is an empirical generalization, not a conceptual truth, and admits systematic counterexamples.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Our current inability to prove P≠NP means the boundary between polynomial and super-polynomial algorithms reflects epistemic, not ontological, limits on computation.
      ?

      Think about whether this reason is strong or weak

    • 2.A claim grounded in the absence of discovered polynomial algorithms conflates the sociology of mathematical discovery with structural facts about computational complexity.
      ?

      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

    SkepticismTruth & Knowledge

    Related

    A claim grounded in the absence of discovered polynomial algorithms conflates th...Cobham-Edmonds thesis conflates worst-case complexity with practical performance...In cases where a function can be uniformly computed for practically relevant inp...In cases where uniform computation is not currently possible, a polynomial time ...
    +3 moreShow less
    Many exponential-time algorithms (e.g., simplex method) perform efficiently in p...Our current inability to prove P≠NP means the boundary between polynomial and su...The correlation between polynomial-time solvability and practical computability ...

    Similar

    Feasibility of an algorithm is characterized by polynomial-time comput...90%The Cobham-Edmonds thesis identifies feasibility with polynomial-time ...86%The Invariance Thesis implies that whether a problem admits a polynomi...85%The Invariance Thesis shows that whether a problem admits a polynomial...85%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    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 values of a function (or decide a problem) for all arguments in which we take interest, it is t
    Extraction notes

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

    Details

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