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
    NSPACE(f(n)) ⊆ TIME(2^O(f(n))) for time and space constru... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Modality & Possibility
    HistoryEditSee Inverse

    NSPACE(f(n)) ⊆ TIME(2^O(f(n))) for time and space constructible 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.A nondeterministic machine with space bound f(n) can be simulated deterministically in exponential time in f(n)
      ?

      Think about whether this reason is strong or weak

    • 2.f(n) is assumed to be both time and space constructible
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The proof relies on enumerating all configurations of a nondeterministic machine, but 'configuration' presupposes a fixed, observer-independent notion of machine state.
      ?

      Think about whether this reason is strong or weak

    • 2.Wittgenstein's rule-following considerations show that no finite description uniquely determines its own extension, undermining the assumption that configurations are determinate.
      ?

      Think about whether this reason is strong or weak

    • 3.If configuration-counting is semantically indeterminate, the 2^O(f(n)) bound is not a discovered mathematical fact but a constructed artifact of a chosen formalism.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The simulation argument assumes that nondeterministic computation is a coherent idealization, but Kripke's skeptical paradox about rule-following applies equally to idealized machine transitions.
      ?

      Think about whether this reason is strong or weak

    • 2.Space constructibility requires that f(n) be computable by a machine that itself presupposes the deterministic-computation framework the theorem is meant to characterize.
      ?

      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 nondeterministic machine with space bound f(n) can be simulated deterministica...If configuration-counting is semantically indeterminate, the 2^O(f(n)) bound is ...Space constructibility requires that f(n) be computable by a machine that itself...The proof relies on enumerating all configurations of a nondeterministic machine...
    +3 moreShow less
    The simulation argument assumes that nondeterministic computation is a coherent ...Wittgenstein's rule-following considerations show that no finite description uni...f(n) is assumed to be both time and space constructible

    Similar

    f(n) is both time and space constructible91%f(n) is assumed to be both time and space constructible91%Savitch's Theorem: for any space constructible function s(n), NSPACE(s...84%For any space constructible function s(n), NSPACE(s(n)) is a subset of...78%

    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