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
    Without a proof that the hierarchy theorem's machine-spec... — Carmelics
    Home
    HistoryEditSee Inverse

    Part of a larger discussion

    Challenges→NP is a proper subset of NEXP

    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.

    ?Rate how convincing each reason is below to see the overall strength.

    No one has weighed in yet. Be the first to share reasons for or against this statement.

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

    Key Terms

    Hierarchy theorem(in computational complexity theory)
    A mathematical result showing that computational problems can be organized into strict levels of difficulty—solving harder problems requires more computing power or time than solving easier ones.
    Machine-specific(in computational theory)
    Results or properties that depend on the particular type of computer or computational model being used, rather than being true for all possible computing devices.
    Outruns its formal justification(in logical argumentation)
    Makes a claim that goes beyond what can actually be proven or supported by the available evidence and logical reasoning.
    Proper subset(mathematical/computational)
    A collection that contains some, but not all, of the items in another collection. For example, all dogs are a proper subset of all animals, since there are animals that aren't dogs.

    Next step

    Based on where you are in your exploration

    Explore a random proposition
    Start fresh with something unrelated.
    Relativization-resistant(in computational complexity)
    A mathematical proof or result that remains true even when you give the computer special helper functions, meaning the proof works in a deeper, more fundamental way.
    Separations (class separations)(in computational complexity)
    Mathematical proofs showing that two groups of computational problems are genuinely different in difficulty—that one class is strictly harder than the other.
    relativization(Used here as a technique for defining metaphysical necessity from epistemic necessity by relativizing to some suitable class)
    A method for defining one form of necessity in terms of another by restricting to a suitable class, applicable when the extension of the target property is broader than the base property

    Connections

    2 topics

    Truth & Knowledge1 linkedModality & Possibility1 linked

    Related

    NP is a proper subset of NEXP

    Details

    Type
    claim
    Perspectives
    0 (0 for, 0 against)
    Edits
    1 edit

    Open for perspectives

    This idea is waiting for its first supporting or challenging perspective.

    Share the first perspective