Lesson plan

PolyL

In computational complexity theory, polyL is the complexity class of decision problems that can be solved on a deterministic Turing machine by an algorithm whose space complexity is bounded by a polylogarithmic function in the size of the input. In other words, polyL = DSPACE((log n) O(1) ), where n denotes the input size, and O(1) denotes a constant. Just as L ⊆ P, polyL ⊆ QP. However, the only proven relationship between polyL and P is that polyL ≠ P; it is unknown if polyL ⊊ P, if P ⊊ polyL, or if neither is contained in the other. The same is true for polyL vs NP. One proof that polyL ≠ P is that P has a complete problem under logarithmic space many-one reductions but polyL does not due to the space hierarchy theorem. The space hierarchy theorem guarantees that DSPACE(log d n) ⊊ DSPACE(log d + 1 n) for all integers d > 0. If polyL had a complete problem, call it A, it would be an element of DSPACE(log k n) for some integer k > 0. Suppose problem B is an element of DSPACE(log k + 1 n) but not of DSPACE(log k n). The assumption that A is complete implies the following O(log k n) space algorithm for B: reduce B to A in logarithmic space, then decide A in O(log k n) space. This implies that B is an element of DSPACE(log k n) and hence violates the space hierarchy theorem.…

Back to article

Article summary

In computational complexity theory, polyL is the complexity class of decision problems that can be solved on a deterministic Turing machine by an algorithm whose space complexity is bounded by a polylogarithmic function in the size of the input. In other words, polyL = DSPACE((log n) O(1) ), where n denotes the input size, and O(1) denotes a constant. Just as L ⊆ P, polyL ⊆ QP. However, the only proven relationship between polyL and P is that polyL ≠ P; it is unknown if polyL ⊊ P, if P ⊊ polyL, or if neither is contained in the other. The same is true for polyL vs NP. One proof that polyL ≠ P is that P has a complete problem under logarithmic space many-one reductions but polyL does not due to the space hierarchy theorem. The space hierarchy theorem guarantees that DSPACE(log d n) ⊊ DSPACE(log d + 1 n) for all integers d > 0. If polyL had a complete problem, call it A, it would be an element of DSPACE(log k n) for some integer k > 0. Suppose problem B is an element of DSPACE(log k + 1 n) but not of DSPACE(log k n). The assumption that A is complete implies the following O(log k n) space algorithm for B: reduce B to A in logarithmic space, then decide A in O(log k n) space. This implies that B is an element of DSPACE(log k n) and hence violates the space hierarchy theorem.…

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.