Complexity class
From Wikipedia, the free encyclopedia
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.
[edit] Relationships between complexity classes
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.
[edit] See also
[edit] Further reading
- 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.
|
|||||
