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:
“There’s one basic rule you should remember about development charts that will save you countless hours of worry.... The fact that a child passes through a particular developmental stage is always more important than the age of that child when he or she does it. In the long run, it really doesn’t matter whether you learn to walk at ten months or fifteen months—as long as you learn how to walk.”
—Lawrence Kutner (20th century)
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)
“There are four classes of idols which beset men’s minds. To these for distinction’s sake I have assigned names—calling the first class Idols of the Tribe; the second, Idols of the Cave; the third, Idols of the Market-Place; the fourth, Idols of the Theatre.”
—Francis Bacon (1561–1626)