Editing Complexity class (section)

{{short description|Set of problems in computational complexity theory}}
[[Image:Complexity subsets pspace.svg|thumb|right|A representation of the relationships between several important complexity classes]]
In [[computational complexity theory]], a '''complexity class''' is a [[set (mathematics)|set]] of [[computational problem]]s "of related resource-based [[computational complexity|complexity]]".{{sfnp|Johnson|1990}} The two most commonly analyzed resources are [[time complexity|time]] and [[space complexity|memory]]. 

In general, a complexity class is defined in terms of a type of computational problem, a [[model of computation]], and a bounded resource like [[time complexity|time]] or [[space complexity|memory]]. In particular, most complexity classes consist of [[decision problem]]s that are solvable with a [[Turing machine]], and are differentiated by their time or space (memory) requirements. For instance, the class '''[[P (complexity)|P]]''' is the set of decision problems solvable by a deterministic Turing machine in [[polynomial time]]. There are, however, many complexity classes defined in terms of other types of problems (e.g. [[Counting problem (complexity)|counting problem]]s and [[function problem]]s) and using other models of computation (e.g. [[probabilistic Turing machine]]s, [[interactive proof system]]s, [[Boolean circuit]]s, and [[quantum computer]]s).

The study of the relationships between complexity classes is a major area of research in [[theoretical computer science]]. There are often general hierarchies of complexity classes; for example, it is known that a number of fundamental time and space complexity classes relate to each other in the following way: [[L (complexity)|'''L''']]⊆'''[[NL (complexity)|NL]]'''&sube;'''[[P (complexity)|P]]'''&sube;'''[[NP (complexity)|NP]]'''&sube;'''[[PSPACE]]'''&sube;'''[[EXPTIME]]'''&sube;'''[[NEXPTIME]]'''⊆'''[[EXPSPACE]]''' (where &sube; denotes the [[subset]] relation). However, many relationships are not yet known; for example, one of the most famous [[open problem]]s in computer science concerns whether [[P versus NP|'''P''' equals '''NP''']]. The relationships between classes often answer questions about the fundamental nature of computation. The '''P''' versus '''NP''' problem, for instance, is directly related to questions of whether [[Nondeterministic algorithm|nondeterminism]] adds any computational power to computers and whether problems having solutions that can be quickly checked for correctness can also be quickly solved.