api: YAML JSON TOON Database
version: 1.0.0
format: yaml
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…
    - 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: 37
  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