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
    L is a proper subset of PSPACE — Carmelics
    Home/Modality & Possibility
    HistoryEditSee Inverse

    Part of a larger discussion

    Supports→At least one of the inclusions L ⊆ NL, NL ⊆ P, P ⊆ NP, or NP ⊆ PSPACE must be proper

    L is a proper subset of PSPACE

    Modality & Possibility
    ?Rate how convincing each reason is below to see the overall strength.
    3 reasons for
    2 reasons against

    Next step

    Based on where you are in your exploration

    Strongest counterpoint
    Explore the most compelling reason on the other side.

    Sign in or register to share your perspective on this statement.

    Reasons For

    3 perspectives
    Reason for 1 of 3
    ?
    • 1.The Space Hierarchy Theorem holds for space constructible functions
      ?

      Think about whether this reason is strong or weak

    • 2.log(n) and n^k satisfy the conditions of the Space Hierarchy Theorem
      ?

      Think about whether this reason is strong or weak

    Reason for 2 of 3
    ?
    • 1.By the Space Hierarchy Theorem, if s1(n)/s2(n) → 0 then SPACE(s1(n)) is a proper subset of SPACE(s2(n))
      ?

      Think about whether this reason is strong or weak

    • 2.log(n) grows strictly slower than any polynomial in n
      ?

      Think about whether this reason is strong or weak

    Reason for 3 of 3
    ?
    • The Time Hierarchy Theorem part iii) implies proper containment between L and PSPACE
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The Space Hierarchy Theorem establishes proper containment between complexity classes only within a formal axiomatic system, not as a mind-independent metaphysical fact.
      ?

      Think about whether this reason is strong or weak

    • 2.Gödel's incompleteness results show that sufficiently expressive formal systems cannot prove all true statements about their own syntactic objects, including complexity class relationships.
      ?

      Think about whether this reason is strong or weak

    • 3.The modal claim that L is *necessarily* a proper subset of PSPACE may be unprovable within the formal systems we use to reason about computation, making 'proper subset' a claim about provability, not possibility.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The Space Hierarchy Theorem presupposes that space-constructible functions are well-defined, but constructibility itself is a notion relative to a model of computation with no canonical metaphysical grounding.
      ?

      Think about whether this reason is strong or weak

    • 2.Relativization results (Baker-Gill-Solovay 1975) demonstrate that there exist oracles relative to which standard separation arguments fail, meaning the hierarchy theorems establish class separation only in unrelativized models.
      ?

      Think about whether this reason is strong or weak

    • 3.A claim of proper subset that holds only within specific, oracle-free computational models does not establish the unrestricted modal claim that L is necessarily a proper subset of PSPACE across all possible computational frameworks.
      ?

      Think about whether this reason is strong or weak

    Topics

    Modality & Possibility

    Connections

    2 topics

    Truth & Knowledge5 linkedAll sources support it1 linked

    Related

    A claim of proper subset that holds only within specific, oracle-free computatio...At least one of the inclusions L ⊆ NL, NL ⊆ P, P ⊆ NP, or NP ⊆ PSPACE must be pr...By the Space Hierarchy Theorem, if s1(n)/s2(n) → 0 then SPACE(s1(n)) is a proper...Gödel's incompleteness results show that sufficiently expressive formal systems ...
    +9 moreShow less
    If none of the intermediate inclusions were proper, L would equal PSPACE, contra...Relativization results (Baker-Gill-Solovay 1975) demonstrate that there exist or...The Space Hierarchy Theorem establishes proper containment between complexity cl...

    Similar

    NP is a proper subset of NEXP100%P is a proper subset of EXP100%L is a proper subset of PSPACE and P is a proper subset of EXP96%It is widely believed that PH is a proper subset of PSPACE95%

    Source

    AI-extracted
    SEP: computational-complexity
    View source passageHide passage
    2 Complexity classes and the hierarchy theorems Recall that a complexity class is a set of languages all of which can be decided within a given time or space complexity bound \(t(n)\) or \(s(n)\) with respect to a fixed model of computation. g. non-recursive ones) it is standard to restrict attention to complexity classes defined when \(t(n)\) and \(s(n)\) are time or space constructible. e. a string of \(n\) 1s) halts after exactly \(t(n)\) steps. Similarly, \(s(n)\) is said to be space constru

    Details

    Type
    premise
    Perspectives
    5 (3 for, 2 against)
    Edits
    1 edit
    The Space Hierarchy Theorem holds for space constructible functions
    The Space Hierarchy Theorem presupposes that space-constructible functions are w...
    The Time Hierarchy Theorem part iii) implies proper containment between L and PS...
    The modal claim that L is *necessarily* a proper subset of PSPACE may be unprova...
    log(n) and n^k satisfy the conditions of the Space Hierarchy Theorem
    log(n) grows strictly slower than any polynomial in n