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
    P ≠ NP is unlikely to be independent of Peano Arithmetic ... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Skepticism
    HistoryEditSee Inverse

    P ≠ NP is unlikely to be independent of Peano Arithmetic or ZFC.

    SkepticismTruth & 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.P ≠ NP is expressible as an arithmetical statement of the form ∀x∃y ψ(x,y) with only bounded numerical quantifiers.
      ?

      Think about whether this reason is strong or weak

    • 2.Such statements are generally believed unlikely to be independent of strong theories like PA.
      ?

      Think about whether this reason is strong or weak

    • 3.There is currently no reason to suspect P ≠ NP is more likely to be independent of PA than other open number-theoretic statements.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Gödel's incompleteness results show that arithmetical statements of low logical complexity can nonetheless be independent of PA, as demonstrated by Paris-Harrington.
      ?

      Think about whether this reason is strong or weak

    • 2.The universality of P≠NP across computational models and its resistance to standard proof techniques mirrors structural features of known independence results.
      ?

      Think about whether this reason is strong or weak

    • 3.Epistemic familiarity with a statement's syntactic form provides no reliable evidence about its provability in a given formal system.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Harvey Friedman's program demonstrates that combinatorial statements with no apparent set-theoretic content can require large cardinal axioms beyond ZFC for their proof.
      ?

      Think about whether this reason is strong or weak

    • 2.The informal consensus that P≠NP is 'probably' unprovable by current methods is epistemically compatible with, and may even suggest, genuine independence rather than mere technical difficulty.
      ?

      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 topic

    Modality & Possibility1 linked

    Related

    Epistemic familiarity with a statement's syntactic form provides no reliable evi...Gödel's incompleteness results show that arithmetical statements of low logical ...Harvey Friedman's program demonstrates that combinatorial statements with no app...P ≠ NP is expressible as an arithmetical statement of the form ∀x∃y ψ(x,y) with ...
    +4 moreShow less
    Such statements are generally believed unlikely to be independent of strong theo...The informal consensus that P≠NP is 'probably' unprovable by current methods is ...The universality of P≠NP across computational models and its resistance to stand...There is currently no reason to suspect P ≠ NP is more likely to be independent ...

    Similar

    The Continuum Hypothesis is independent of ZFC91%The Continuum Hypothesis is independent of ZFC (ZFC cannot decide whet...90%Aristotle's comparison of Alcmaeon to the Pythagoreans in Metaphysics ...84%It is believed that P ≠ NP is unlikely to be independent of strong the...84%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    1 On the significance of \(\textbf{P} \neq \textbf{NP}\)? The appreciation of complexity theory outside of theoretical computer science is largely due to the notoriety of open questions such as 1–4. \) – has attracted the greatest attention. e. the Millennium Problems (Cook 2006). g. (Sipser 1992), (Fortnow 2009), and (Fortnow 2013). \) will prove to have far reaching practical and theoretical consequences outside of computer science. Perhaps the most significant of these revolves around the pos
    Extraction notes

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

    Details

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