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
    A proof of P ≠ NP is beyond the reach of currently known ... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Skepticism
    HistoryEditSee Inverse

    A proof of P ≠ NP is beyond the reach of currently known proof techniques.

    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.Known proof methods such as diagonalization relativize and therefore cannot separate P from NP.
      ?

      Think about whether this reason is strong or weak

    • 2.Approaches such as geometric complexity theory are still in need of substantial refinement.
      ?

      Think about whether this reason is strong or weak

    • 3.No currently known method is sufficient to yield the desired separation between P and NP.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Razborov and Rudich's natural proofs barrier presupposes strong pseudorandom function assumptions; if one-way functions do not exist, the barrier dissolves.
      ?

      Think about whether this reason is strong or weak

    • 2.The claim that proof techniques are insufficient conflates contingent cryptographic assumptions with necessary logical limitations on mathematical method.
      ?

      Think about whether this reason is strong or weak

    • 3.A proof technique blocked under one set of background assumptions may become viable if those assumptions are revised, so the barrier is conditional, not absolute.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The relativization barrier (Baker-Gill-Solovay) shows diagonalization fails, but non-relativizing techniques like arithmetization already exist and succeeded in proving IP=PSPACE.
      ?

      Think about whether this reason is strong or weak

    • 2.The existence of at least one successful non-relativizing proof method refutes the inductive generalization that no currently known technique can yield complexity separations.
      ?

      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

    No other argument is better1 linked

    Related

    A proof technique blocked under one set of background assumptions may become via...Approaches such as geometric complexity theory are still in need of substantial ...Known proof methods such as diagonalization relativize and therefore cannot sepa...No currently known method is sufficient to yield the desired separation between ...
    +4 moreShow less
    Razborov and Rudich's natural proofs barrier presupposes strong pseudorandom fun...The claim that proof techniques are insufficient conflates contingent cryptograp...The existence of at least one successful non-relativizing proof method refutes t...The relativization barrier (Baker-Gill-Solovay) shows diagonalization fails, but...

    Similar

    A proof of P ≠ NP is beyond the reach of currently known proof techniq...99%A proof of P ≠ NP is beyond the reach of current techniques98%The problem is considered by the research community to exceed the capa...83%Mathematics is a motley of techniques of proof and does not require a ...83%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    For in this case a demonstration that \(\phi \not\in n\text{-}\sc{PROVABILITY}_{\mathsf{T}}\) (for a sufficiently large \(n\) and a sufficiently powerful \(\mathsf{T}\)) would be sufficient to show that we have no hope of ever comprehending a proof of \(\phi\) even if one were to exist. But now note that since \(n\text{-}\sc{PROVABILITY}_{\mathsf{T}} \in \textbf{NP}\), if it so happened that \(\textbf{P} = \textbf{NP}\) then the task of determining whether a mathematical formula is derivable in
    Extraction notes

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

    Details

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