Lesson plan

EXPSPACE

In computational complexity theory, is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in O(2^{p(n)}) space, where p(n) is a polynomial function of n . Some authors restrict p(n) to be a linear function, but most authors instead call the resulting class . If we use a nondeterministic machine instead, we get the class , which is equal to by Savitch's theorem. A decision problem is if it is in , and every problem in has a polynomial-time many-one reduction to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. problems might be thought of as the hardest problems in . is a strict superset of , , and . It contains and is believed to strictly contain it, but this is unproven.

Back to article

Article summary

In computational complexity theory, is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in O(2^{p(n)}) space, where p(n) is a polynomial function of n . Some authors restrict p(n) to be a linear function, but most authors instead call the resulting class . If we use a nondeterministic machine instead, we get the class , which is equal to by Savitch's theorem. A decision problem is if it is in , and every problem in has a polynomial-time many-one reduction to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. problems might be thought of as the hardest problems in . is a strict superset of , , and . It contains and is believed to strictly contain it, but this is unproven.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.