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
    NP is a proper subset of NEXP — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Modality & Possibility
    HistoryEditSee Inverse

    NP is a proper subset of NEXP

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

    Reasons For

    3 perspectives
    Reason for 1 of 3
    ?
    • 1.The Nondeterministic Time Hierarchy Theorem holds
      ?

      Think about whether this reason is strong or weak

    • 2.The functions n^k and 2^(n^k) satisfy the conditions of the Nondeterministic Time Hierarchy Theorem
      ?

      Think about whether this reason is strong or weak

    Reason for 2 of 3
    ?
    • 1.By the Non-deterministic Time Hierarchy Theorem, if t1(n+1)/t2(n) → 0 then NTIME(t1(n)) is a proper subset of NTIME(t2(n))
      ?

      Think about whether this reason is strong or weak

    • 2.The relevant polynomial and exponential functions satisfy this hypothesis
      ?

      Think about whether this reason is strong or weak

    Reason for 3 of 3
    ?
    • The Time Hierarchy Theorem part ii) implies proper containment between NP and NEXP
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The Nondeterministic Time Hierarchy Theorem presupposes that nondeterministic computation is a coherent, well-defined model of physical possibility.
      ?

      Think about whether this reason is strong or weak

    • 2.The Church-Turing thesis underdetermines whether nondeterministic Turing machines correspond to any realizable computational process.
      ?

      Think about whether this reason is strong or weak

    • 3.A theorem whose premises invoke physically unrealizable models yields conclusions whose modal force is limited to mathematical, not computational, necessity.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The inference from NTIME(t1) ⊊ NTIME(t2) to NP ⊊ NEXP conflates complexity classes defined by worst-case bounds with classes defined by problem families.
      ?

      Think about whether this reason is strong or weak

    • 2.Hartmanis and Stearns's original hierarchy theorems apply to specific machines, not to the robust, machine-independent classes NP and NEXP as standardly defined.
      ?

      Think about whether this reason is strong or weak

    • 3.Without a proof that the hierarchy theorem's machine-specific separations lift uniformly to relativization-resistant class separations, the proper subset claim outruns its formal justification.
      ?

      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

    Connections

    1 topic

    All sources support it2 linked

    Related

    A theorem whose premises invoke physically unrealizable models yields conclusion...By the Non-deterministic Time Hierarchy Theorem, if t1(n+1)/t2(n) → 0 then NTIME...Hartmanis and Stearns's original hierarchy theorems apply to specific machines, ...The Church-Turing thesis underdetermines whether nondeterministic Turing machine...
    +7 moreShow less
    The Nondeterministic Time Hierarchy Theorem holdsThe Nondeterministic Time Hierarchy Theorem presupposes that nondeterministic co...The Time Hierarchy Theorem part ii) implies proper containment between NP and NE...The functions n^k and 2^(n^k) satisfy the conditions of the Nondeterministic Tim...The inference from NTIME(t1) ⊊ NTIME(t2) to NP ⊊ NEXP conflates complexity class...The relevant polynomial and exponential functions satisfy this hypothesisWithout a proof that the hierarchy theorem's machine-specific separations lift u...

    Similar

    P is a proper subset of EXP100%L is a proper subset of PSPACE100%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-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
    5 (3 for, 2 against)
    Edits
    1 edit