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:
“Minimize, eliminate, delegate, and routinize. Decide what’s important and forget the rest”
—Donna N. Douglass (20th century)
“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)
“My plan of instruction is extremely simple and limited. They learn, on week-days, such coarse works as may fit them for servants. I allow of no writing for the poor. My object is not to make fanatics, but to train up the lower classes in habits of industry and piety.”
—Hannah More (1745–1833)