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
    If the equality P=coP were trivially entailed by closure ... — Carmelics
    Home
    HistoryEditSee Inverse

    Part of a larger discussion

    Challenges→P equals coP

    If the equality P=coP were trivially entailed by closure properties alone, it would collapse the polynomial hierarchy in ways inconsistent with widely accepted complexity-theoretic conjectures such as PH being infinite.

    ?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

    Closure properties(analogous concept in complexity theory)
    In mathematics and logic, the quality of a system being 'closed' when operations performed on its elements always produce results that also belong to the system.
    P=coP(computational complexity theory)
    A proposed equality between two classes of computational problems—P (problems solvable quickly) and coP (problems whose 'no' answers are verifiable quickly). The statement questions whether these two categories are actually the same.
    Polynomial Hierarchy (PH)(Generalization of the NP/coNP distinction to multiple levels of quantifier alternation.)
    A hierarchy of complexity classes based on the logical representation of computational problems, built by alternating existential and universal quantification, with Δ⁰_P = Σ⁰_P = Π⁰_P = P at the base.
    collapse (in complexity theory)(computer science)
    When different levels of problem difficulty turn out to be the same, like discovering that 'hard' and 'easy' problems are actually equivalent.

    Next step

    Based on where you are in your exploration

    Explore a random proposition
    Start fresh with something unrelated.
    complexity-theoretic conjectures(theoretical computer science)
    Educated guesses by computer scientists about the limits of what problems can be solved efficiently, which are widely believed but not yet proven.
    trivially entailed(logic and mathematics)
    Something that follows obviously or automatically from a set of rules, without needing any special argument or proof.

    Connections

    2 topics

    Truth & Knowledge1 linkedModality & Possibility1 linked

    Related

    P equals coP

    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