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
    The Polynomial Hierarchy collapses if either the Buss hie... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Modality & Possibility
    HistoryEditSee Inverse

    The Polynomial Hierarchy collapses if either the Buss hierarchy of theories collapses at some level or S_2 (or T_2) is finitely axiomatizable

    Modality & PossibilityTruth & 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.The provably total functions of S^i_2 correspond to the i-th level of the Polynomial Hierarchy
      ?

      Think about whether this reason is strong or weak

    • 2.If there exists i such that T^i_2 = S^{i+1}_2, the corresponding levels of the Polynomial Hierarchy coincide
      ?

      Think about whether this reason is strong or weak

    • 3.If S_2 or T_2 is finitely axiomatizable, the union hierarchy collapses to a finite level, collapsing the Polynomial Hierarchy correspondingly
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The correspondence between provably total functions of S^i_2 and Σ^p_i relies on Buss's witnessing theorem, which itself assumes consistency of the theories involved.
      ?

      Think about whether this reason is strong or weak

    • 2.Gödel's second incompleteness theorem entails that S_2 cannot prove its own consistency, so the collapse inference operates outside the system it purports to characterize.
      ?

      Think about whether this reason is strong or weak

    • 3.A hierarchy collapse demonstrated only in a metatheory stronger than S_2 may be epistemically inaccessible to the very computational agents whose complexity it claims to describe.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Finite axiomatizability of S_2 or T_2 is an open problem, and modal epistemologists following Williamson hold that possibility claims require more than the absence of known refutations.
      ?

      Think about whether this reason is strong or weak

    • 2.The conditional structure 'if X collapses then PH collapses' conveys no information about the actual modal status of PH unless the antecedent condition is independently motivated as genuinely possible.
      ?

      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

    Modality & PossibilityTruth & Knowledge

    Connections

    1 topic

    Philosophy of Language1 linked

    Related

    A hierarchy collapse demonstrated only in a metatheory stronger than S_2 may be ...Finite axiomatizability of S_2 or T_2 is an open problem, and modal epistemologi...Gödel's second incompleteness theorem entails that S_2 cannot prove its own cons...If S_2 or T_2 is finitely axiomatizable, the union hierarchy collapses to a fini...
    +4 moreShow less
    If there exists i such that T^i_2 = S^{i+1}_2, the corresponding levels of the P...The conditional structure 'if X collapses then PH collapses' conveys no informat...The correspondence between provably total functions of S^i_2 and Σ^p_i relies on...The provably total functions of S^i_2 correspond to the i-th level of the Polyno...

    Similar

    If either the hierarchy of theories S^i_2, T^i_2 collapses or S_2 or T...98%It is not known whether the hierarchies of theories S^i_2 and T^i_2 co...93%The finite axiomatizability of S_2 or T_2 entails the collapse of the ...86%If S_2 or T_2 is finitely axiomatizable, the union hierarchy collapses...86%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    A first link between formal arithmetic and complexity was provided by Cobham’s (1965) original characterization of \(\textbf{FP}\) in terms of a functional algebra similar to that by which the primitive recursive functions are defined. 1 The function \(f(\vec{x},y)\) is said to be defined from \(g(\vec{x}), h_0(\vec{x},y,z), h_1(\vec{x},y,z)\) and \(k(\vec{x},y)\) by limited recursion on notation just in case \[ \begin{aligned} f(\vec{x},0) &= g(\vec{x})\\ f(\vec{x},s_0(y)) &= h_0(\v
    Extraction notes

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

    Details

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