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 system P_1 admits proofs of PHP_n of size polynomial ... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Modality & Possibility
    HistoryEditSee Inverse

    The system P_1 admits proofs of PHP_n of size polynomial in n.

    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
    ?
    • Buss (1987) demonstrated that P_1 has polynomial-size proofs of PHP_n.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Polynomial-size proof existence is a syntactic, complexity-theoretic notion that does not track the semantic difficulty of recognizing why PHP_n is true.
      ?

      Think about whether this reason is strong or weak

    • 2.Cook and Reckhow's framework conflates proof length with proof comprehensibility, obscuring that short formal derivations may require exponential search to discover.
      ?

      Think about whether this reason is strong or weak

    • 3.A genuine account of provability must distinguish between the existence of a proof and the feasibility of finding it, as Kreisel's work on proof theory demands.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Buss's proof of PHP_n in P_1 encodes induction over sharply bounded formulas, which presupposes the very combinatorial principles PHP is meant to test.
      ?

      Think about whether this reason is strong or weak

    • 2.A proof system that builds in the resources needed to derive a principle cannot serve as independent evidence that the principle is 'easily provable' in any epistemically meaningful sense.
      ?

      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

    Related

    A genuine account of provability must distinguish between the existence of a pro...A proof system that builds in the resources needed to derive a principle cannot ...Buss (1987) demonstrated that P_1 has polynomial-size proofs of PHP_n.Buss's proof of PHP_n in P_1 encodes induction over sharply bounded formulas, wh...
    +2 moreShow less
    Cook and Reckhow's framework conflates proof length with proof comprehensibility...Polynomial-size proof existence is a syntactic, complexity-theoretic notion that...

    Similar

    Buss (1987) showed that P1 admits proofs of PHP_n of size polynomial i...92%P_1 admits polynomial-size proofs of PHP_n.88%A system that admits polynomial-size proofs of PHP_n is not shown to b...87%Buss (1987) demonstrated that P_1 has polynomial-size proofs of PHP_n.86%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    Haken showed that any resolution proof of \(\text{PHP}_n\) must have size at least exponential in \(n\). From this it follows that resolution is not polynomially bounded. However, it was later shown by Buss (1987) that the system \(\mathcal{P}_1\) (and hence also systems like \(\mathcal{P}_2\), \(\mathcal{P}_3\) which can be shown to efficiently simulate \(\mathcal{P}_1\)) do admit proofs of \(\text{PHP}_n\) which are of size polynomial in \(n\). One subsequent direction of research in proof co
    Extraction notes

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

    Details

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