Complexity Classes

Key computational complexity classes and the problems they contain.

  • Algorithms
  • 21 entries
  • 7 sections
  • CC0 — public domain

The data

0

Class
P
Description
Problems solvable in polynomial time by a deterministic Turing machine.
Example
Sorting, shortest path, linear search

1

Class
NP
Description
Problems verifiable in polynomial time by a deterministic TM.
Example
SAT, Hamiltonian Path, Subset Sum

2

Class
NP-Complete
Description
The hardest problems in NP; all can be reduced to each other.
Example
SAT, Knapsack, Traveling Salesman (decision version)

3

Class
NP-Hard
Description
At least as hard as the hardest problems in NP.
Example
Halting Problem (undecidable), TSP optimization

4

Class
BPP
Description
Problems solvable in polynomial time with bounded error by a probabilistic TM.
Example
Primality testing (AKP primality test)

5

Class
L
Description
Problems solvable using logarithmic space.
Example
Graph connectivity, planar graph isomorphism

6

Class
PSPACE
Description
Problems solvable using polynomial space.
Example
Quantified Boolean formulas, games

Fetch the same bytes

The static files are identical to what the API returns, but with no rate limit and no server round trip. Use the API when you want a query and a content type; use the files when you want to cache one document. 

curl "https://yjtoon.com/api/dataset/complexity-classes?format=toon"
const res = await fetch(
  "https://yjtoon.com/static-data/dataset/complexity-classes.toon"
);
const toon = await res.text();

Rate limit: 120 requests per minute per IP, no key and no signup. API reference →

Topics

  • algorithms
  • complexity
  • p-vs-np
  • computability