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:
“Ideals possess the strange quality that if they were completely realized they would turn into nonsense. One could easily follow a commandment such as “Thou shalt not kill” to the point of dying of starvation; and I might establish the formula that for the proper functioning of the mesh of our ideals, as in the case of a strainer, the holes are just as important as the mesh.”
—Robert Musil (1880–1942)
“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)
“The want of education and moral training is the only real barrier that exists between the different classes of men. Nature, reason, and Christianity recognize no other. Pride may say Nay; but Pride was always a liar, and a great hater of the truth.”
—Susanna Moodie (1803–1885)