Complexity Classes
Key computational complexity classes and the problems they contain.
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 it 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.
Watch out for
- 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.
The data
13 rows
| 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 |
Fields
The shape of this dataset, read from the data itself: every column, its type and a real value. Agents can use this to plan a query without fetching the whole document.
| 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 |
Fetch the same bytes
The static files contain the same reference rows as the API, with no API rate limit. Live metadata, such as view counts, may differ. Use the API for content negotiation; use the static files for a cacheable snapshot.
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 →