List of complexity classes

From Academic Kids

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).

#PCount solutions to an NP problem
#P-completeThe hardest problems in #P
APXOptimization problems that have approximation algorithms with constant approximation ratio
AMSolvable in polynomial time by an Arthur-Merlin protocol
BPPSolvable in polynomial time by randomized algorithms (answer is probably right)
BQPSolvable in polynomial time on a quantum computer (answer is probably right)
Co-NP"NO" answers checkable in polynomial time
Co-NP-completeThe hardest problems in Co-NP
DSPACE(f(n))Solvable by a deterministic machine in space O(f(n)).
DTIME(f(n))Solvable by a deterministic machine in time O(f(n)).
ESolvable in exponential time with linear exponent
ELEMENTARYThe union of the classes in the exponential hierarchy
ESPACESolvable in exponential space with linear exponent
EXPSame as EXPTIME
EXPSPACESolvable in exponential space
EXPTIMESolvable with exponential time
FNPThe analogue of NP for function problems
FPThe analogue of P for function problems
FPNPThe analogue of PNP for function problems; the home of the traveling salesman problem
FPTFixed-parameter tractable
IPSolvable in polynomial time by an interactive proof system
LSolvable in logarithmic (small) space
MASolvable in polynomial time by a Merlin-Arthur protocol
NCSolvable efficiently (in polylogarithmic time) on parallel computers
NESolvable by a non-deterministic machine in exponential time with linear exponent
NESPACESolvable by a non-deterministic machine in exponential space with linear exponent
NEXPSame as NEXPTIME
NEXPSPACESolvable by a non-deterministic machine in exponential space
NEXPTIMESolvable by a non-deterministic machine in exponential time
NL"YES" answers checkable in logarithmic space
NP"YES" answers checkable in polynomial time (see complexity classes P and NP)
NP-completeThe hardest or most expressive problems in NP
NP-easyAnalogue to PNP for function problems; another name for FPNP
NP-equivalentThe hardest problems in FPNP
NP-hardEither NP-complete or harder
NSPACE(f(n))Solvable by a non-deterministic machine in space O(f(n)).
NTIME(f(n))Solvable by a non-deterministic machine in time O(f(n)).
PSolvable in polynomial time
P-completeThe hardest problems in P to solve on parallel computers
PCPProbabilistically Checkable Proof
PHThe union of the classes in the polynomial hierarchy
PNPSolvable in polynomial time with an oracle for a problem in NP; also known as Δ2P
PPProbabilistically Polynomial (answer is right with probability slightly more than ½)
PSPACESolvable with polynomial memory and unlimited time
PSPACE-completeThe hardest problems in PSPACE
RLSolvable in logarithmic space by randomized algorithms (NO answer is probably right, YES is certainly right)
RPSolvable in polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right)
RLPSolvable in logarithmic space and polynomial time by randomized algorithms (NO answer is probably right, YES is certainly right)
SLProblems 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.
UPUnambiguous Non-Deterministic Polytime functions.
ZPPSolvable by randomized algorithms (answer is always right, average running time is polynomial)

External link

es:Lista de clases de complejidad

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools