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
    The Boolean Halting Problem (BHP) is in P only if P equal... — Carmelics
    Home/Truth & Knowledge
    HistoryEditSee Inverse

    The Boolean Halting Problem (BHP) is in P only if P equals NP

    Proof of definition segmentsTruth & 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.BHP is NP-complete
      ?

      Think about whether this reason is strong or weak

    • 2.NP is closed under polynomial-time reductions
      ?

      Think about whether this reason is strong or weak

    • 3.If a problem is NP-complete and in P, then P = NP
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The claim presupposes that NP-completeness is a property stable across all formal systems, but Gödelian incompleteness suggests completeness classifications may be system-relative.
      ?

      Think about whether this reason is strong or weak

    • 2.If the NP-completeness of BHP is provable only within systems that already assume P≠NP, the conditional 'BHP ∈ P → P=NP' is trivially vacuous rather than informative.
      ?

      Think about whether this reason is strong or weak

    • 3.A conditional with an unprovably false antecedent (per Scott Aaronson's 'algebrization' barrier results) yields no epistemic traction about the actual structure of P versus NP.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Polynomial-time reducibility as a canonical equivalence relation depends on the Church-Turing thesis applied to feasibility, which Wilfried Sieg and others treat as a substantive empirical assumption.
      ?

      Think about whether this reason is strong or weak

    • 2.If 'feasible computation' is not co-extensional with polynomial time across all physically realizable models, the closure property of NP under polynomial reductions loses its unconditional force.
      ?

      Think about whether this reason is strong or weak

    • 3.The logical step from NP-completeness to P=NP therefore inherits the modal fragility of the feasibility thesis rather than standing as a purely formal entailment.
      ?

      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

    Truth & KnowledgeProof of definition segments

    Connections

    1 topic

    All sources support it1 linked

    Related

    A conditional with an unprovably false antecedent (per Scott Aaronson's 'algebri...BHP is NP-completeIf 'feasible computation' is not co-extensional with polynomial time across all ...If a problem is NP-complete and in P, then P = NP
    +5 moreShow less
    If the NP-completeness of BHP is provable only within systems that already assum...NP is closed under polynomial-time reductionsPolynomial-time reducibility as a canonical equivalence relation depends on the ...The claim presupposes that NP-completeness is a property stable across all forma...The logical step from NP-completeness to P=NP therefore inherits the modal fragi...

    Similar

    BHP is in P only if P equals NP98%BHP is in P only if P = NP94%BHP is in P only if P = NP.92%PSPACE equals NPSPACE (PSPACE = NPSPACE)84%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    Since \(\sc{BHP}\) is \(\textbf{NP}\)-complete, it follows from the closure of \(\textbf{NP}\) under \(\leq_P\) that this problem is in \(\textbf{P}\) only if \(\textbf{P} = \textbf{NP}\). Since this is widely thought not to be the case, this provides some evidence that \(\sc{BHP}\) is an intrinsically difficult computational problem. But since \(\sc{BHP}\) is closely related to the model of computation \(\mathfrak{N}\) itself this may appear to be of little practical significance. It is thus of
    Extraction notes

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

    Details

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