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
    At least one of the inclusions among L, P, NP, PSPACE, an... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Modality & Possibility
    HistoryEditSee Inverse

    At least one of the inclusions among L, P, NP, PSPACE, and EXP must be proper

    Modality & Possibility
    ?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.L is a proper subset of PSPACE and P is a proper subset of EXP
      ?

      Think about whether this reason is strong or weak

    • 2.The chain L ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP must include at least one proper inclusion to account for the known separations at its ends
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The inference from known endpoint separations (L⊊PSPACE, P⊊EXP) to an intermediate proper inclusion commits the fallacy of assuming transitivity of witness.
      ?

      Think about whether this reason is strong or weak

    • 2.Knowing that a chain A⊆B⊆C satisfies A⊊C does not logically entail which intermediate link is proper without independent diagonalization or oracle separation for that link.
      ?

      Think about whether this reason is strong or weak

    • 3.The supporting argument thus smuggles in a distributional assumption about where separation occurs that the mathematics does not yet license.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Epistemic humility in formal ontology, as urged by Penelope Maddy's naturalism, requires distinguishing what is proven from what is structurally suggested by incomplete evidence.
      ?

      Think about whether this reason is strong or weak

    • 2.The claim 'at least one inclusion is proper' is presented as established fact, yet it rests on no single proof that directly witnesses a proper inclusion within the chain L⊆P⊆NP⊆PSPACE.
      ?

      Think about whether this reason is strong or weak

    • 3.Conflating the modal claim 'some inclusion must be proper' with the epistemically stronger 'we know which one' obscures that the claim's truth-value is currently grounded in inference, not demonstration.
      ?

      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

    Conflating the modal claim 'some inclusion must be proper' with the epistemicall...Epistemic humility in formal ontology, as urged by Penelope Maddy's naturalism, ...Knowing that a chain A⊆B⊆C satisfies A⊊C does not logically entail which interme...L is a proper subset of PSPACE and P is a proper subset of EXP
    +4 moreShow less
    The chain L ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP must include at least one proper inclusion t...The claim 'at least one inclusion is proper' is presented as established fact, y...The inference from known endpoint separations (L⊊PSPACE, P⊊EXP) to an intermedia...The supporting argument thus smuggles in a distributional assumption about where...

    Similar

    At least one of the inclusions L ⊆ NL, NL ⊆ P, P ⊆ NP, NP ⊆ PSPACE mus...92%At least one of the inclusions L ⊆ NL, NL ⊆ P, P ⊆ NP, or NP ⊆ PSPACE ...92%The Polynomial Hierarchy (PH) is properly contained in PSPACE, i.e., P...79%L is properly contained in PSPACE (L ⊊ PSPACE)78%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    As \(\phi \in \sc{SAT}\) just in case a satisfying valuation exists, this is a correct method for deciding \(\sc{SAT}\) relative to conventions (i)–(iii) from above. This means that \(\sc{SAT}\) can be solved in polynomial time relative to \(\mathfrak{N}\). This example also illustrates why adding non-determinism to the original deterministic model \(\mathfrak{T}\) does not enlarge the class of decidable problems. [12] It is evident that if \(N\) has time complexity \(f(n)\), then \(T_N\) must
    Extraction notes

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

    Details

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