api: YAML JSON TOON Database
version: 1.0.0
format: toon
dataset:
  id: 2754
  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[2]: 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[2]: "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[4]: backtracking-algorithms,dynamic-programming-patterns,greedy-algorithms,cryptographic-algorithms
  entry_count: 13
  fields[3]{section,field,type,example}:
    data,class,string,P
    data,description,string,Problems solvable in polynomial time by a deter…
    data,example,string,"Sorting, shortest path, linear search"
  category: Algorithms
  category_slug: algorithms
  tags: "algorithms,complexity,p-vs-np,computability"
  view_count: 39
  created_at: 1793403093
  updated_at: 1793403093
data[13]{class,description,example}:
  P,Problems solvable in polynomial time by a deterministic Turing machine.,"Sorting, shortest path, linear search"
  NP,Problems verifiable in polynomial time by a deterministic TM.,"SAT, Hamiltonian Path, Subset Sum"
  NP-Complete,The hardest problems in NP; all can be reduced to each other.,"SAT, Knapsack, Traveling Salesman (decision version)"
  NP-Hard,At least as hard as the hardest problems in NP.,"Halting Problem (undecidable), TSP optimization"
  BPP,Problems solvable in polynomial time with bounded error by a probabilistic TM.,Primality testing (AKP primality test)
  L,Problems solvable using logarithmic space.,"Graph connectivity, planar graph isomorphism"
  PSPACE,Problems solvable using polynomial space.,"Quantified Boolean formulas, games"
  co-NP,Problems whose complements are in NP; a 'no' answer has a short certificate.,Tautology checking (Is a formula always true?)
  NL,Problems solvable by a nondeterministic Turing machine using logarithmic space.,Directed graph reachability
  EXPTIME,Problems solvable in exponential time by a deterministic Turing machine.,Generalized chess and checkers on n-by-n boards
  BQP,Problems solvable in polynomial time by a quantum computer with bounded error.,Integer factorization (Shor's algorithm)
  "#P","Counting problems: the number of accepting paths of an NP machine.",Counting satisfying assignments of a formula
  ZPP,Problems solvable by randomized algorithms that always give the right answer in expected polynomial time.,Primality testing with zero-error variants