Complexity class

From Wikipedia, the free encyclopedia

(Redirected from Complexity classes)
Jump to: navigation, search

In computational complexity theory, a complexity class is a set of problems of related complexity. A typical complexity class has a definition of the form:

the set of problems that can be solved by abstract machine M using O(f(n)) of resource R (n is the size of the input)

For example, the class NP is the set of decision problems that can be solved by a non-deterministic Turing machine in polynomial time, while the class PSPACE is the set of decision problems that can be solved by a deterministic Turing machine in polynomial space. Some complexity classes are sets of function problems, such as FP.

Many complexity classes can be characterized in terms of the mathematical logic needed to express them; see descriptive complexity.

The Blum axioms can be used to define complexity classes without referring to a concrete computational model.

The following table shows some of the classes of problems (or languages, or grammars) that are considered in complexity theory. If class X is a strict subset of Y, then X is shown below Y, with a dark line connecting them. If X is a subset, but it is unknown whether they are equal sets, then the line is lighter and is dotted. Technically, the breakdown into decidable and undecidable pertains more to the study of computability theory but is useful for putting the complexity classes in perspective.

Decision Problem
image:solidLine.png image:solidLine.png
Type 0 (Recursively enumerable)
Undecidable
image:solidLine.png
Decidable
image:solidLine.png
EXPSPACE
image:dottedLine.png
EXPTIME
image:dottedLine.png
PSPACE
image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png
Type 1 (Context Sensitive)
image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png
PSPACE-Complete
image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png
image:solidLine.png image:solidLine.png
Co-NP
image:dottedLine.png image:dottedLine.png
NP
image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png
image:solidLine.png image:solidLine.png image:dottedLine.png
BPP
BQP
NP-Complete
image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png image:dottedLine.png
image:solidLine.png image:solidLine.png
P
image:solidLine.png image:solidLine.png image:dottedLine.png image:dottedLine.png
image:solidLine.png
NC
P-Complete
image:solidLine.png image:solidLine.png
Type 2 (Context Free)
image:solidLine.png
Type 3 (Regular)

  • The Complexity Zoo: A huge list of complexity classes, as reference for experts.
  • Diagram by Neil Immerman showing the hierarchy of complexity classes and how they fit together.
  • Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. The standard reference on NP-Complete problems - an important category of problems whose solutions appear to require an impractically long time to compute.

v • d • e
Important complexity classes (more)
P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH
Retrieved from "http://en.wikipedia.org/wiki/Complexity_class"
Advanced Search
Included Web Search Engines


Safe Search

close

Top Matching Results

Occasionally Search.com will highlight specialized results that are based on the context of your query. Examples of specialized results include specific links to news, images, or video.

Top Matching Results may highlight information from other Search.com pages, content from the CNET Network of sites, or third party content. The listings are based purely on relevance. Search.com does not receive payment for listings in this section but our partners that provide this data may get paid for listing these products.

Sponsored Links

This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Search.com sends your search query to several search engines at one time and integrates the results into one list which has been sorted by relevance using Search.com's proprietary algorithm. You can customize the list of search engines included in your metasearch from the preferences.

The search engines that are used in your metasearch may allow companies to pay to have their Web sites included within the results. To view the Paid Inclusion policy for a specific search engine, please visit their Web site. Search.com does not accept payment or share revenue with any search engine partner for listings in this section.