Complexity Theory Markus Bläser, Balagopal Komarath

News

Chandra, Kozen, Stockmeyer

Written: 12.11.2019 10:14 Written By: Balagopal Komarath

Alternation

The introduction states some cool theorems that you can prove in this model. One of them is that time-bounds become space-bounds and space-bounds become time-bounds when moving between deterministic and alternating TMs.

The definition of ATMs given in the paper is more complex because it deals with the following case: If one branch of an existential guess halts and accepts, then you can consider the subcomputation  as an accept even if some other branch is non-halting. However, Theorem 2.6 in this paper proves that as long as we are only considering ATMs with nice time and space bounds, we can assume that all branches halt within that bound. This assumption is true for us since we are only considering poly-time bounded machines.



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators