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
    Oracle-relative results (Baker, Gill, Solovay 1975) demon... — Carmelics
    Home
    HistoryEditSee Inverse

    Part of a larger discussion

    Challenges→Complexity classes like P are closed under complementation

    Oracle-relative results (Baker, Gill, Solovay 1975) demonstrate that structural properties like closure under complement can fail or hold contingently depending on the computational environment.

    ?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

    Baker, Gill, Solovay(computer science history)
    Three computer scientists (Theodore Baker, John Gill, and Robert Solovay) who published influential research in 1975 about the limits of what computers can solve.
    Closure under complement(mathematical logic)
    A property where if you take any rule or solution that works in a system, the opposite rule or solution also works in that same system—imagine a game where every winning move has a losing opposite.
    Computational environment(computer science)
    The specific setup or conditions under which a computer does its work—like the rules and resources available to solve a problem.
    Oracle-relative results(computational complexity theory)
    Mathematical findings that show how answers to certain questions can change depending on what extra information or 'shortcuts' (called oracles) you're allowed to use—like comparing different possible rule books for a game.

    Next step

    Based on where you are in your exploration

    Explore a random proposition
    Start fresh with something unrelated.
    contingently(in modal logic)
    In a way that could be true or false; depending on specific circumstances rather than being required by logic or nature.
    structural properties(Maxwell's distinction used to rebut Kripke's challenge to the mind-brain identity theory)
    Properties of brain events that are revealed by common sense, physics, and neurophysiology, as opposed to underlying non-structural (qualitative/phenomenal) properties

    Connections

    1 topic

    Truth & Knowledge1 linked

    Related

    Complexity classes like P are closed under complementation

    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