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
    It is unlikely that a polynomial time algorithm exists fo... — Carmelics
    Home/Skepticism
    HistoryEditSee Inverse

    It is unlikely that a polynomial time algorithm exists for any NP-complete problem.

    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.Extensive effort has been devoted to finding efficient solutions for particular NP-complete problems such as INTEGER PROGRAMMING and TSP.
      ?

      Think about whether this reason is strong or weak

    • 2.No polynomial time algorithm has been found for any NP-complete problem despite this extensive effort.
      ?

      Think about whether this reason is strong or weak

    • 3.The existence of a polynomial time algorithm for any NP-complete problem would imply polynomial time algorithms for all problems in NP, which runs strongly counter to expectation.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Absence of discovered proof is not evidence of absence, as Hume's problem of induction warns against inferring universal laws from finite empirical records.
      ?

      Think about whether this reason is strong or weak

    • 2.The history of mathematics contains numerous problems resistant to solution for centuries before breakthroughs occurred, including Fermat's Last Theorem and the primality testing problem.
      ?

      Think about whether this reason is strong or weak

    • 3.The argument from 'extensive effort' tacitly assumes human mathematical ingenuity has adequately explored the solution space, an epistemically unjustified presumption.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The supporting argument conflates pragmatic unlikelihood with logical impossibility, a modal fallacy that Kripke's framework on necessity and possibility explicitly warns against.
      ?

      Think about whether this reason is strong or weak

    • 2.P=NP remaining unproven means current complexity theory cannot rule out the existence of a polynomial algorithm, making 'unlikely' a sociological claim rather than a mathematical one.
      ?

      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

    Connections

    1 linked claim

    The existence of a polynomial time algorithm for any NP-complete problem would r...

    Related

    Absence of discovered proof is not evidence of absence, as Hume's problem of ind...Extensive effort has been devoted to finding efficient solutions for particular ...No polynomial time algorithm has been found for any NP-complete problem despite ...P=NP remaining unproven means current complexity theory cannot rule out the exis...
    +5 moreShow less
    The argument from 'extensive effort' tacitly assumes human mathematical ingenuit...The existence of a polynomial time algorithm for any NP-complete problem would i...The existence of a polynomial time algorithm for any NP-complete problem would r...The history of mathematics contains numerous problems resistant to solution for ...The supporting argument conflates pragmatic unlikelihood with logical impossibil...

    Similar

    The existence of a polynomial time algorithm for any NP-complete probl...95%The existence of a polynomial time algorithm for any NP-complete probl...95%No polynomial time algorithm has been found for any NP-complete proble...94%The existence of a polynomial time algorithm for any single NP-complet...93%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    It also follows from the transitivity of \(\leq_P\) that the existence of a polynomial time algorithm for even one \(\textbf{NP}\)-complete problem would entail the existence of polynomial time algorithms for all problems in \(\textbf{NP}\). The existence of such an algorithm would thus run strongly counter to expectation in virtue of the extensive effort which has been devoted to finding efficient solutions for particular \(\textbf{NP}\)-complete problems such as \(\sc{INTEGER}\ \sc{PROGRAMMING
    Extraction notes

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

    Details

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