api: "YAML JSON TOON Database"
version: "1.0.0"
format: "json"
dataset:
  slug: "complexity-classes"
  title: "Complexity Classes"
  description: "Key computational complexity classes and the problems they contain."
  category: "Algorithms"
  category_slug: "algorithms"
  tags: "algorithms,complexity,p-vs-np,computability"
  view_count: 0
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"