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
    Diagonalization cannot be used to separate P from NP. — Carmelics
    Home/Skepticism
    HistoryEditSee Inverse

    Diagonalization cannot be used to separate P from NP.

    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.Baker, Gill, and Solovay (1975) established oracles A and B such that P^A = NP^A and P^B ≠ NP^B.
      ?

      Think about whether this reason is strong or weak

    • 2.A proof of P ≠ NP based on diagonalization would relativize to both oracle A and oracle B.
      ?

      Think about whether this reason is strong or weak

    • 3.A method that relativizes to both A and B cannot separate P and NP, since P^A = NP^A.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Non-relativizing proof techniques (e.g., arithmetization used in IP=PSPACE) demonstrate that oracle barriers do not constrain all possible proof strategies.
      ?

      Think about whether this reason is strong or weak

    • 2.The Baker-Gill-Solovay result shows diagonalization-based proofs cannot resolve P vs NP, not that diagonalization itself is categorically excluded as a component of a hybrid proof.
      ?

      Think about whether this reason is strong or weak

    • 3.A proof incorporating diagonalization alongside non-relativizing elements would not be subject to the relativization barrier, leaving the claim's scope critically under-specified.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The relativization barrier is a property of proof methods, not of mathematical facts, so oracle separation results constrain epistemology, not the underlying separation itself.
      ?

      Think about whether this reason is strong or weak

    • 2.Razborov and Rudich's natural proofs barrier and Aaronson and Wigderson's algebrization barrier each identify distinct obstacles, implying no single barrier argument is sufficient to foreclose all diagonalization variants.
      ?

      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

    3 topics

    All sources support it1 linkedCausation1 linkedModality & Possibility1 linked

    Related

    A method that relativizes to both A and B cannot separate P and NP, since P^A = ...A proof incorporating diagonalization alongside non-relativizing elements would ...A proof of P ≠ NP based on diagonalization would relativize to both oracle A and...Baker, Gill, and Solovay (1975) established oracles A and B such that P^A = NP^A...
    +4 moreShow less
    Non-relativizing proof techniques (e.g., arithmetization used in IP=PSPACE) demo...Razborov and Rudich's natural proofs barrier and Aaronson and Wigderson's algebr...

    Similar

    Diagonalization cannot be used to separate P and NP.99%Diagonalization cannot be used to separate P from NP99%There are few known candidates for separating BPP from P85%Nothing can be separate from itself.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

    The Baker-Gill-Solovay result shows diagonalization-based proofs cannot resolve ...
    The relativization barrier is a property of proof methods, not of mathematical f...
    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit