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.
Many of these classes have a 'Co' partner which consists of the complements of all languages in the original class. For example if a language 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.)
"The hardest problems" of a class refer to problems, which belong to the class and every other problem of that class can be reduced to it. Furthermore, the reduction is also a problem of the given class, or its subset.
If you don't see a class listed (such as Co-UP) you should look under its partner (such as UP).
External links
* [http://qwiki.caltech.edu/wiki/Complexity_Zoo Complexity Zoo] - list of over 400 complexity classes and their properties
Wikimedia Foundation.
2010.
Look at other dictionaries:
Complexity class — In computational complexity theory, a complexity class is a set of problems of related resource based complexity. A typical complexity class has a definition of the form: the set of problems that can be solved by an abstract machine M using… … Wikipedia
List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… … Wikipedia
List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic … Wikipedia
List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… … Wikipedia
List of algorithm general topics — This is a list of algorithm general topics, by Wikipedia page. * Analysis of algorithms * Ant colony algorithm * Approximation algorithm * Best and worst cases * Big O notation * Combinatorial search * Competitive analysis * Computability theory… … Wikipedia
List of mathematical examples — This page will attempt to list examples in mathematics. To qualify for inclusion, an article should be about a mathematical object with a fair amount of concreteness. Usually a definition of an abstract concept, a theorem, or a proof would not be … Wikipedia
List of University of Michigan alumni — There are more than 425,000 living alumni of the University of Michigan. Famous alumni include the father of the iPod, the founders of Sun Microsystems and Google, the father of information theory, the voice of Darth Vader, the first doctor… … Wikipedia
Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… … Wikipedia
Complexity of constraint satisfaction — The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction… … Wikipedia
List of common misconceptions — This incomplete list is not intended to be exhaustive. This is a list of current, widely held, false ideas and beliefs about notable topics which have been reported by reliable sources from around the world. Each has been discussed in published… … Wikipedia
