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 P vs NP remains open, the semantic content of 'proper ... — Carmelics
    Home
    HistoryEditSee Inverse

    Part of a larger discussion

    Challenges→P is a proper subset of TIME(f(n)) for any super-polynomial time bound f(n)

    If P vs NP remains open, the semantic content of 'proper subset' in complexity theory may be underdetermined in ways that weaken extensional confidence in related hierarchy claims.

    ?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

    Complexity theory(where analogous issues might appear)
    A branch of computer science and mathematics that studies how difficult different problems are to solve and how much computational power they require.
    Hierarchy claims(as used in complexity theory and logic)
    Statements that different categories, levels, or types of things can be ranked or ordered from simpler to more complex.
    P vs NP(the general computational problem being restricted by the theorem)
    One of the most important unsolved problems in computer science asking whether two different classes of problems (those easy to solve and those easy to check) are actually the same.
    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.
    extensional(logic and philosophy of probability)
    A property of relations (like material implication) that Nagel claimed Reichenbach's probability implication lacks
    semantic content(Cappelen and Lepore's literalist/minimalist framework)
    Propositions determined solely by conventions of meaning, precisification, disambiguation, and reference fixing — not by pragmatic inference.
    underdetermined(Used to contrast mathematical conjectures, whose correct answers are fixed by logical facts, with cases where no such determination exists.)
    A decision or truth is underdetermined when logical facts alone do not fix a single correct answer.

    Connections

    2 topics

    Truth & Knowledge1 linkedModality & Possibility1 linked

    Related

    P is a proper subset of TIME(f(n)) for any super-polynomial time bound f(n)

    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