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 L ⊆ NL, NL ⊆ P, P ⊆ NP, NP... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Modality & Possibility
    HistoryEditSee Inverse

    At least one of the inclusions L ⊆ NL, NL ⊆ P, P ⊆ NP, NP ⊆ PSPACE 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 properly contained in PSPACE
      ?

      Think about whether this reason is strong or weak

    • 2.If all four inclusions were equalities, L would equal PSPACE, contradicting the proper containment
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The proof that L ⊊ PSPACE relies on the space hierarchy theorem, which itself presupposes the robustness of the Turing machine model as the canonical computational substrate.
      ?

      Think about whether this reason is strong or weak

    • 2.If computational complexity classes are model-relative rather than model-invariant, the 'proper containment' of L in PSPACE may reflect artifact of the Turing formalism rather than an absolute mathematical fact.
      ?

      Think about whether this reason is strong or weak

    • 3.Cobham-Edmonds thesis disputes that Turing machine resource bounds track an objective notion of feasibility, undermining the claim that hierarchy theorems reveal mind-independent structural truths.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The disjunctive conclusion 'at least one inclusion is proper' is a theorem of classical logic applied to set-theoretic containment, but its epistemic status depends on whether mathematical existence is constructively or platonistically interpreted.
      ?

      Think about whether this reason is strong or weak

    • 2.Under strict constructivism in the tradition of Brouwer and Bishop, a proof that not-all-are-equalities does not constructively exhibit which specific inclusion is proper, leaving the disjunction epistemically inert.
      ?

      Think about whether this reason is strong or weak

    • 3.A disjunction lacking a constructive witness—where we cannot currently prove any single disjunct—fails to constitute genuine mathematical knowledge by intuitionist standards, even if classically valid.
      ?

      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 disjunction lacking a constructive witness—where we cannot currently prove any...Cobham-Edmonds thesis disputes that Turing machine resource bounds track an obje...If all four inclusions were equalities, L would equal PSPACE, contradicting the ...If computational complexity classes are model-relative rather than model-invaria...
    +4 moreShow less
    L is properly contained in PSPACEThe disjunctive conclusion 'at least one inclusion is proper' is a theorem of cl...The proof that L ⊊ PSPACE relies on the space hierarchy theorem, which itself pr...Under strict constructivism in the tradition of Brouwer and Bishop, a proof that...

    Similar

    At least one of the inclusions L ⊆ NL, NL ⊆ P, P ⊆ NP, or NP ⊆ PSPACE ...99%At least one of the inclusions among L, P, NP, PSPACE, and EXP must be...92%The chain L ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP must include at least one proper i...80%L is a proper subset of PSPACE and P is a proper subset of EXP78%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    Similarly, parts i) and ii) respectively implies that \(\textbf{P} \subsetneq \textbf{EXP}\) and \(\textbf{NP} \subsetneq \textbf{NEXP}\). And it similarly follows from part iii) that \(\textbf{L} \subsetneq \textbf{PSPACE}\). Note that since every deterministic Turing machine is, by definition, a non-deterministic machine, we clearly have \(\textbf{P} \subseteq \textbf{NP}\) and \(\textbf{PSPACE} \subseteq \textbf{NPSPACE}\). 2 Suppose that \(f(n)\) is both time and space constructible. Then
    Extraction notes

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

    Details

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