
This is a list of complexity classes in computational complexity theory. For other computational and complexity subjects, see list of computability and complexity topics. See computation for a chart showing which classes are subsets of other classes. Many of these classes have a 'Co' partner which consists of the complements of all languages in the original class. For example if L is in NP then the complement of L is in Co-NP. (This doesn't mean that the complement of NP is Co-NP - there are languages which are known to be in both, and other languages which are known to be in neither.) If you don't see a class listed (such as Co-UP) you should look under its partner (such as UP). {| |Sharp-P||Count solutions to an NP problem |- |Sharp-P-complete||The hardest problems in #P |- |APX||Optimization problems that have approximation algorithms with constant approximation ratio |- |Arthur-Merlin protocol||Solvable in polynomial time by an Arthur-Merlin protocol |- |BPP||Solvable in polynomial time by randomized algorithms (answer is probably right) |- |BQP||Solvable in polynomial time on a quantum computer (answer is probably right) |- |Co-NP||"NO" answers checkable in polynomial time |- |Co-NP-complete||The hardest problems in Co-NP |- |DSPACE||Solvable by a deterministic machine in space O(f(''n'')). |- |DTIME||Solvable by a deterministic machine in time O(f(''n'')). |- |E (complexity)||Solvable in exponential time with linear exponent |- |ELEMENTARY||The union of the classes in the exponential hierarchy |- |ESPACE||Solvable in exponential space with linear exponent |- |EXP||Same as EXPTIME |- |EXPSPACE||Solvable in exponential space |- |EXPTIME||Solvable with exponential time |- |FNP (complexity)||The analogue of NP for function problems |- |FP (complexity)||The analogue of P for function problems |- |FPNP||The analogue of PNP for function problems; the home of the traveling salesman problem |- |Fixed-parameter tractable||Fixed-parameter tractable |- |Interactive proof system||Solvable in polynomial time by an interactive proof system |- |L (complexity)||Solvable in logarithmic (small) space |- |Arthur-Merlin protocol||Solvable in polynomial time by a Arthur-Merlin protocol |- |NC (complexity)||Solvable efficiently (in polylogarithmic time) on parallel computers |- |NE (complexity)||Solvable by a non-deterministic machine in exponential time with linear exponent |- |NESPACE||Solvable by a non-deterministic machine in exponential space with linear exponent |- |NEXP||Same as NEXPTIME |- |NEXPSPACE||Solvable by a non-deterministic machine in exponential space |- |NEXPTIME||Solvable by a non-deterministic machine in exponential time |- |NL (complexity)||"YES" answers checkable in logarithmic space |- |NP (complexity)||"YES" answers checkable in polynomial time (see complexity classes P and NP) |- |NP-complete||The hardest or most expressive problems in NP |- |NP-easy||Analogue to PNP for function problems; another name for FPNP |- |NP-equivalent||The hardest problems in FPNP |- |NP-hard||Either NP-complete or harder |- |NSPACE||Solvable by a non-deterministic machine in space O(f(''n'')). |- |NTIME||Solvable by a non-deterministic machine in time O(f(''n'')). |- |P (complexity)||Solvable in polynomial time |- |P-complete||The hardest problems in P to solve on parallel computers |- |probabilistically checkable proof||Probabilistically Checkable Proof |- |PH (complexity)||The union of the classes in the polynomial hierarchy |- |PNP||Solvable in polynomial time with an oracle machine for a problem in NP; also known as Δ2P |- |PP (complexity)||Probabilistically Polynomial (answer is right with probability slightly more than ½) |- |PSPACE||Solvable with polynomial memory and unlimited time |- |PSPACE-complete||The hardest problems in PSPACE |- |RL (complexity)||Solvable in logarithmic space by randomized algorithms (NO answer is probably right, YES is certainly right) |- |RP||Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right) |- |RLP||Solvable in logarithmic space and polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right) |- |SL (complexity)||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 (complexity). |- |UP (complexity)||Unambiguous Non-Deterministic Polytime functions. |- |ZPP||Solvable by randomized algorithms (answer is always right, average running time is polynomial) |} ==External link== *[http://www.complexityzoo.com Complexity Zoo] - list of over 400 complexity classes and their properties complexity classes
See other meanings of words starting from letter:
Words begining with List_of_complexity_classes:
List_of_complexity_classes
List of complexity classes
This is a list of complexity classes in computational complexity theory. For other computational and complexity subjects, see list of computability and complexity topics. See computation for a chart showing which classes are subsets of other classes. Many of these classes have a 'Co' partner which consists of the complements of all languages in the original class. For example if L is in NP then the complement of L is in Co-NP. (This doesn't mean that the complement of NP is Co-NP - there are languages which are known to be in both, and other languages which are known to be in neither.) If you don't see a class listed (such as Co-UP) you should look under its partner (such as UP). {| |Sharp-P||Count solutions to an NP problem |- |Sharp-P-complete||The hardest problems in #P |- |APX||Optimization problems that have approximation algorithms with constant approximation ratio |- |Arthur-Merlin protocol||Solvable in polynomial time by an Arthur-Merlin protocol |- |BPP||Solvable in polynomial time by randomized algorithms (answer is probably right) |- |BQP||Solvable in polynomial time on a quantum computer (answer is probably right) |- |Co-NP||"NO" answers checkable in polynomial time |- |Co-NP-complete||The hardest problems in Co-NP |- |DSPACE||Solvable by a deterministic machine in space O(f(''n'')). |- |DTIME||Solvable by a deterministic machine in time O(f(''n'')). |- |E (complexity)||Solvable in exponential time with linear exponent |- |ELEMENTARY||The union of the classes in the exponential hierarchy |- |ESPACE||Solvable in exponential space with linear exponent |- |EXP||Same as EXPTIME |- |EXPSPACE||Solvable in exponential space |- |EXPTIME||Solvable with exponential time |- |FNP (complexity)||The analogue of NP for function problems |- |FP (complexity)||The analogue of P for function problems |- |FPNP||The analogue of PNP for function problems; the home of the traveling salesman problem |- |Fixed-parameter tractable||Fixed-parameter tractable |- |Interactive proof system||Solvable in polynomial time by an interactive proof system |- |L (complexity)||Solvable in logarithmic (small) space |- |Arthur-Merlin protocol||Solvable in polynomial time by a Arthur-Merlin protocol |- |NC (complexity)||Solvable efficiently (in polylogarithmic time) on parallel computers |- |NE (complexity)||Solvable by a non-deterministic machine in exponential time with linear exponent |- |NESPACE||Solvable by a non-deterministic machine in exponential space with linear exponent |- |NEXP||Same as NEXPTIME |- |NEXPSPACE||Solvable by a non-deterministic machine in exponential space |- |NEXPTIME||Solvable by a non-deterministic machine in exponential time |- |NL (complexity)||"YES" answers checkable in logarithmic space |- |NP (complexity)||"YES" answers checkable in polynomial time (see complexity classes P and NP) |- |NP-complete||The hardest or most expressive problems in NP |- |NP-easy||Analogue to PNP for function problems; another name for FPNP |- |NP-equivalent||The hardest problems in FPNP |- |NP-hard||Either NP-complete or harder |- |NSPACE||Solvable by a non-deterministic machine in space O(f(''n'')). |- |NTIME||Solvable by a non-deterministic machine in time O(f(''n'')). |- |P (complexity)||Solvable in polynomial time |- |P-complete||The hardest problems in P to solve on parallel computers |- |probabilistically checkable proof||Probabilistically Checkable Proof |- |PH (complexity)||The union of the classes in the polynomial hierarchy |- |PNP||Solvable in polynomial time with an oracle machine for a problem in NP; also known as Δ2P |- |PP (complexity)||Probabilistically Polynomial (answer is right with probability slightly more than ½) |- |PSPACE||Solvable with polynomial memory and unlimited time |- |PSPACE-complete||The hardest problems in PSPACE |- |RL (complexity)||Solvable in logarithmic space by randomized algorithms (NO answer is probably right, YES is certainly right) |- |RP||Solvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right) |- |RLP||Solvable in logarithmic space and polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right) |- |SL (complexity)||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 (complexity). |- |UP (complexity)||Unambiguous Non-Deterministic Polytime functions. |- |ZPP||Solvable by randomized algorithms (answer is always right, average running time is polynomial) |} ==External link== *[http://www.complexityzoo.com Complexity Zoo] - list of over 400 complexity classes and their properties complexity classes
See other meanings of words starting from letter:
L
LA | LB | LC | LD | LE | LF | LG | LH | LI | LJ | LK | LM | LN | LO | LP | LR | LS | LT | LU | LW | LX | LY | LZ |Words begining with List_of_complexity_classes:
List_of_complexity_classes
These materials are based on Wikipedia and licensed under the GNU FDL
YouTube.com videos better site than Turbo Tax 2007
