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
    NTIME(f(n)) is a subset of SPACE(f(n)) — Carmelics
    Home/Modality & Possibility
    HistoryEditSee Inverse

    NTIME(f(n)) is a subset of SPACE(f(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
    ?
    • 1.f(n) is both time and space constructible
      ?

      Think about whether this reason is strong or weak

    • 2.A non-deterministic machine with running time f(n) can be simulated by a deterministic machine using space proportional to f(n)
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The simulation argument conflates computational resource bounds with epistemic accessibility: knowing f(n) bounds time does not entail f(n) suffices for space in all models.
      ?

      Think about whether this reason is strong or weak

    • 2.Constructibility assumptions smuggle in a non-trivial ontological commitment — that resources are measurable by the same machine — which fails for non-uniform or oracle-augmented complexity classes.
      ?

      Think about whether this reason is strong or weak

    • 3.Hartmanis and Stearns's original resource-bounded framework presupposes a fixed machine model, making the subset relation model-relative rather than an absolute inclusion claim.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The argument structure equivocates between 'simulation' as logical reduction and 'simulation' as physical realizability, a distinction Turing himself acknowledged in his 1950 distinction between discrete and continuous machines.
      ?

      Think about whether this reason is strong or weak

    • 2.If space reuse across computation branches is permitted in the deterministic simulation, the correctness of the simulation depends on confluence properties that are not guaranteed by f(n)-time bounds alone.
      ?

      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 non-deterministic machine with running time f(n) can be simulated by a determi...Constructibility assumptions smuggle in a non-trivial ontological commitment — t...Hartmanis and Stearns's original resource-bounded framework presupposes a fixed ...If space reuse across computation branches is permitted in the deterministic sim...
    +3 moreShow less
    The argument structure equivocates between 'simulation' as logical reduction and...The simulation argument conflates computational resource bounds with epistemic a...f(n) is both time and space constructible

    Similar

    NSPACE(f(n)) is a subset of TIME(2^O(f(n)))100%PSPACE is a subset of NPSPACE (PSPACE ⊆ NPSPACE)84%P is a subset of NP (P ⊆ NP)84%PSPACE is a subset of NPSPACE83%

    Source

    AI-extracted1/3 agreementValid
    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
    Extraction notes

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

    Details

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