#P> | ount solutions to an NP problem | | a href="/encyclopedia/Sharp-P-complete" title="Sharp-P-complete">#P-complete | The hardest problems in #P |
| a href="/encyclopedia/Arthur-Merlin-protocol" title="Arthur-Merlin protocol">AM | Solvable in polynomial time by an Arthur-Merlin protocol |
| a href="/encyclopedia/BPP" title="BPP">BPP | Solvable in polynomial time by randomized algorithms (answer is probably right) |
| a href="/encyclopedia/BQP" title="BQP">BQP | Solvable in polynomial time on a quantum computer (answer is probably right) |
| a href="/encyclopedia/Co-NP" title="Co-NP">Co-NP | "NO" answers checkable in polynomial time |
| a href="/encyclopedia/Co-NP-complete" title="Co-NP-complete">Co-NP-complete | The hardest problems in Co-NP |
| a href="/encyclopedia/DSPACE" title="DSPACE">DSPACE(f(n)) | Solvable by a deterministic machine in space O(f(n)). |
| a href="/encyclopedia/DTIME" title="DTIME">DTIME(f(n)) | Solvable by a deterministic machine in time O(f(n)). |
| a href="/encyclopedia/E-(complexity)" title="E (complexity)">E | Solvable in exponential time with linear exponent |
| a href="/encyclopedia/ELEMENTARY" title="ELEMENTARY">ELEMENTARY | The union of the classes in the exponential hierarchy |
| a href="/encyclopedia/ESPACE" title="ESPACE">ESPACE | Solvable in exponential space with linear exponent |
| a href="/encyclopedia/EXP" title="EXP">EXP | Same as EXPTIME |
| a href="/encyclopedia/EXPSPACE" title="EXPSPACE">EXPSPACE | Solvable in exponential space |
| a href="/encyclopedia/EXPTIME" title="EXPTIME">EXPTIME | Solvable with exponential time |
| a href="/encyclopedia/FNP-(complexity)" title="FNP (complexity)">FNP | The analogue of NP for function problems |
| a href="/encyclopedia/FP-(complexity)" title="FP (complexity)">FP | The analogue of P for function problems |
| PNP | The analogue of PNP for function problems; the home of the traveling salesman problem |
| a href="/encyclopedia/Fixed-parameter-tractable" title="Fixed-parameter tractable">FPT | Fixed-parameter tractable |
| a href="/encyclopedia/Interactive-proof-system" title="Interactive proof system">IP | Solvable in polynomial time by an interactive proof system |
| a href="/encyclopedia/L-(complexity)" title="L (complexity)">L | Solvable in logarithmic (small) space |
| a href="/encyclopedia/Arthur-Merlin-protocol" title="Arthur-Merlin protocol">MA | Solvable in polynomial time by a Merlin-Arthur protocol |
| a href="/encyclopedia/NC-(complexity)" title="NC (complexity)">NC | Solvable efficiently (in polylogarithmic time) on parallel computers |
| a href="/encyclopedia/NE-(complexity)" title="NE (complexity)">NE | Solvable by a non-deterministic machine in exponential time with linear exponent |
| a href="/encyclopedia/NESPACE" title="NESPACE">NESPACE | Solvable by a non-deterministic machine in exponential space with linear exponent |
| a href="/encyclopedia/NEXP" title="NEXP">NEXP | Same as NEXPTIME |
| a href="/encyclopedia/NEXPSPACE" title="NEXPSPACE">NEXPSPACE | Solvable by a non-deterministic machine in exponential space |
| a href="/encyclopedia/NEXPTIME" title="NEXPTIME">NEXPTIME | Solvable by a non-deterministic machine in exponential time |
| a href="/encyclopedia/NL-(complexity)" title="NL (complexity)">NL | "YES" answers checkable in logarithmic space |
| a href="/encyclopedia/NP-(complexity)" title="NP (complexity)">NP | "YES" answers checkable in polynomial time (see complexity classes P and NP) |
| a href="/encyclopedia/NP-complete" title="NP-complete">NP-complete | The hardest or most expressive problems in NP |
| a href="/encyclopedia/NP-easy" title="NP-easy">NP-easy | Analogue to PNP for function problems; another name for FPNP |
| a href="/encyclopedia/NP-equivalent" title="NP-equivalent">NP-equivalent | The hardest problems in FPNP |
| a href="/encyclopedia/NP-hard" title="NP-hard">NP-hard | Either NP-complete or harder |
| a href="/encyclopedia/NSPACE" title="NSPACE">NSPACE(f(n)) | Solvable by a non-deterministic machine in space O(f(n)). |
| a href="/encyclopedia/NTIME" title="NTIME">NTIME(f(n)) | Solvable by a non-deterministic machine in time O(f(n)). |
| a href="/encyclopedia/P-(complexity)" title="P (complexity)">P | Solvable in polynomial time |
| a href="/encyclopedia/P-complete" title="P-complete">P-complete | The hardest problems in P to solve on parallel computers |
| a href="/encyclopedia/probabilistically-checkable-proof" title="probabilistically checkable proof">PCP | Probabilistically Checkable Proof |
| a href="/encyclopedia/PH-(complexity)" title="PH (complexity)">PH | The union of the classes in the polynomial hierarchy |
| NP | Solvable in polynomial time with an oracle for a problem in NP; also known as Δ2P |
| a href="/encyclopedia/PP-(complexity)" title="PP (complexity)">PP | Probabilistically Polynomial (answer is right with probability slightly more than ) |
| a href="/encyclopedia/PSPACE" title="PSPACE">PSPACE | Solvable with polynomial memory and unlimited time |
| a href="/encyclopedia/PSPACE-complete" title="PSPACE-complete">PSPACE-complete | The hardest problems in PSPACE |
| a href="/encyclopedia/RL-(complexity)" title="RL (complexity)">RL | Solvable in logarithmic space by randomized algorithms (NO answer is probably right, YES is certainly right) |
| a href="/encyclopedia/RP" title="RP">RP | Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right) |
| a href="/encyclopedia/RLP" title="RLP">RLP | Solvable in logarithmic space and polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right) |
| a href="/encyclopedia/SL-(complexity)" title="SL (complexity)">SL | Problems log-space reducible to determining if a path exist between given vertices in an undirected graph. In October 2004 it was discovered that this class is in fact equal to L. |
| a href="/encyclopedia/UP-(complexity)" title="UP (complexity)">UP | Unambiguous Non-Deterministic Polytime functions. |
| a href="/encyclopedia/ZPP" title="ZPP">ZPP | Solvable by randomized algorithms (answer is always right, average running time is polynomial) |