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
  [7]{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"