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:
““A man has got to keep his extrication.
The important thing is not to get bogged down
In what he has to do to earn a living....””
—Robert Frost (1874–1963)
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)
“There are two classes of men called poets. The one cultivates life, the other art,... one satisfies hunger, the other gratifies the palate.”
—Henry David Thoreau (1817–1862)