{
    "api": "YAML JSON TOON Database",
    "version": "1.0.0",
    "format": "json",
    "dataset": {
        "id": 2344,
        "slug": "complexity-classes",
        "title": "Complexity Classes",
        "description": "Key computational complexity classes and the problems they contain.",
        "summary": "The principal computational complexity classes with a description and examples: P, NP, NP-complete, NP-hard, BPP, L and PSPACE, plus co-NP, NL, EXPTIME, BQP, #P and ZPP.",
        "use_when": [
            "You need the definition of a complexity class and a canonical problem.",
            "You are judging whether a problem is believed to be efficiently solvable."
        ],
        "caveats": [
            "Many relationships between classes are conjectured and unproven, including P versus NP.",
            "Class membership concerns worst-case behavior of the best algorithm, not typical instances."
        ],
        "related": [
            "backtracking-algorithms",
            "dynamic-programming-patterns",
            "greedy-algorithms",
            "cryptographic-algorithms"
        ],
        "entry_count": 13,
        "fields": [
            {
                "section": "data",
                "field": "class",
                "type": "string",
                "example": "P"
            },
            {
                "section": "data",
                "field": "description",
                "type": "string",
                "example": "Problems solvable in polynomial time by a deter\u2026"
            },
            {
                "section": "data",
                "field": "example",
                "type": "string",
                "example": "Sorting, shortest path, linear search"
            }
        ],
        "category": "Algorithms",
        "category_slug": "algorithms",
        "tags": "algorithms,complexity,p-vs-np,computability",
        "view_count": 36,
        "created_at": 1792832553,
        "updated_at": 1792832553
    },
    "data": [
        {
            "class": "P",
            "description": "Problems solvable in polynomial time by a deterministic Turing machine.",
            "example": "Sorting, shortest path, linear search"
        },
        {
            "class": "NP",
            "description": "Problems verifiable in polynomial time by a deterministic TM.",
            "example": "SAT, Hamiltonian Path, Subset Sum"
        },
        {
            "class": "NP-Complete",
            "description": "The hardest problems in NP; all can be reduced to each other.",
            "example": "SAT, Knapsack, Traveling Salesman (decision version)"
        },
        {
            "class": "NP-Hard",
            "description": "At least as hard as the hardest problems in NP.",
            "example": "Halting Problem (undecidable), TSP optimization"
        },
        {
            "class": "BPP",
            "description": "Problems solvable in polynomial time with bounded error by a probabilistic TM.",
            "example": "Primality testing (AKP primality test)"
        },
        {
            "class": "L",
            "description": "Problems solvable using logarithmic space.",
            "example": "Graph connectivity, planar graph isomorphism"
        },
        {
            "class": "PSPACE",
            "description": "Problems solvable using polynomial space.",
            "example": "Quantified Boolean formulas, games"
        },
        {
            "class": "co-NP",
            "description": "Problems whose complements are in NP; a 'no' answer has a short certificate.",
            "example": "Tautology checking (Is a formula always true?)"
        },
        {
            "class": "NL",
            "description": "Problems solvable by a nondeterministic Turing machine using logarithmic space.",
            "example": "Directed graph reachability"
        },
        {
            "class": "EXPTIME",
            "description": "Problems solvable in exponential time by a deterministic Turing machine.",
            "example": "Generalized chess and checkers on n-by-n boards"
        },
        {
            "class": "BQP",
            "description": "Problems solvable in polynomial time by a quantum computer with bounded error.",
            "example": "Integer factorization (Shor's algorithm)"
        },
        {
            "class": "#P",
            "description": "Counting problems: the number of accepting paths of an NP machine.",
            "example": "Counting satisfying assignments of a formula"
        },
        {
            "class": "ZPP",
            "description": "Problems solvable by randomized algorithms that always give the right answer in expected polynomial time.",
            "example": "Primality testing with zero-error variants"
        }
    ]
}