Important Complexity Classes
Many important complexity classes can be defined by bounding the time or space used by the algorithm. Some important complexity classes of decision problems defined in this manner are the following:
| Complexity class | Model of computation | Resource constraint |
|---|---|---|
| DTIME(f(n)) | Deterministic Turing machine | Time f(n) |
| P | Deterministic Turing machine | Time poly(n) |
| EXPTIME | Deterministic Turing machine | Time 2poly(n) |
| NTIME(f(n)) | Non-deterministic Turing machine | Time f(n) |
| NP | Non-deterministic Turing machine | Time poly(n) |
| NEXPTIME | Non-deterministic Turing machine | Time 2poly(n) |
| DSPACE(f(n)) | Deterministic Turing machine | Space f(n) |
| L | Deterministic Turing machine | Space O(log n) |
| PSPACE | Deterministic Turing machine | Space poly(n) |
| EXPSPACE | Deterministic Turing machine | Space 2poly(n) |
| NSPACE(f(n)) | Non-deterministic Turing machine | Space f(n) |
| NL | Non-deterministic Turing machine | Space O(log n) |
| NPSPACE | Non-deterministic Turing machine | Space poly(n) |
| NEXPSPACE | Non-deterministic Turing machine | Space 2poly(n) |
It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem.
Other important complexity classes include BPP, ZPP and RP, which are defined using probabilistic Turing machines; AC and NC, which are defined using boolean circuits and BQP and QMA, which are defined using quantum Turing machines. #P is an important complexity class of counting problems (not decision problems). Classes like IP and AM are defined using Interactive proof systems. ALL is the class of all decision problems.
Read more about this topic: Complexity Class
Famous quotes containing the words important, complexity and/or classes:
“The Oregon [matter] and the annexation of Texas are now all- important to the security and future peace and prosperity of our union, and I hope there are a sufficient number of pure American democrats to carry into effect the annexation of Texas and [extension of] our laws over Oregon. No temporizing policy or all is lost.”
—Andrew Jackson (1767–1845)
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)
“Solidity, caution, integrity, efficiency. Lack of imagination, hypocrisy. These qualities characterize the middle classes in every country, but in England they are national characteristics.”
—E.M. (Edward Morgan)