Polynomial Time Machines

A Turing Machine can be determinisitic, non-deterministic or alternating. Under a polynomial time limitation, it is unclear whether any of these are a strict super-sets of the other. The classes are \(\text{P}, \text{NP}, \text{AP}\) respectively. What's interesting is \(\text{AP} = \text{PSPACE}\). The relation between these three classes is as follows:

\[ \text{P} \stackrel{\subseteq}{\tiny ?} \text{NP} \stackrel{\subseteq}{\tiny ?} \text{PSPACE} \]

It is conjectured that all the subsets are strict. Cook-Levin Theorem required the locality of computation to produce the NP-completeness of SAT. Referring to Arora Barak's textbook on Complexity Theory, they guess that to make these subset equalities stricter, there is a need to use a new property of computation and/or the Turing Machine.

Another Resource

Apart from space and time, you can treat non-determinism and alternation as resources as well. The greater non-determinism comes from a larger witness, greater alternation comes from the number of times the ATM is allowed to alternate. The polynomial heirarchy forms a heirarchy based on the number of alternations that are allowed. At the end, these alternations serve no additional benefit if the total time allocated is locked to polynomial. Any amount of alternation with polynomial time resource is equivalent of having polynomial space with no alternation at all.

Alternation itself allowed with polynomial space is equivalent of having exponential time (\(\text{APSPACE} = \text{EXPTIME}\)). The time and space heirarchy theorems talk about time and space as resource, and how having more of it provides us with power to decide more languages. Polynomial heirarchy does something similar, but under constrained time. Polynomial heirarchy talks about the power of alternating between existential and universal quantifiers. Just like non-determinism, it is unclear if alternations offer any advantage over determinism under polynomial time.

References

  • Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak
  • Lecture 17 of Complexity Theory: Markus Krötzsch