Alternation

Alternation is a generalization of nondeterminism that has proven to be useful in understanding relationships among complexity classes, simplifying various proofs in complexity theory

Definition: An alternating Turing machine is a nondeterministic Turing machine whose states are divided into universal states and existential states; when we run an alternating Turing machine on an input

• A universal state is accepting if all of its children are accepting
• An existential state is accepting if any of its children are accepting
• The input is accepted if the start node is designated accepting

An alternating Turing machine with only existential states is a classic nondeterministic Turing machine

Definition: $\mathbf{ATIME}(t(n))$ is the set of languages decided by an $O(t(n))$ time alternating Time machine, and $\mathbf{ASPACE}(f(n))$ is the set of languages decided by an $O(f(n))$ space alternating Turing machine

We also define $\mathbf{AP}$, $\mathbf{APSPACE}$, and $\mathbf{AL}$ as polynomial time, polynomial space, and logarithmic space respectively

Example:
A tautalogy is a Boolean formula that always evaluates to 1

We can easily decide $TAUT=\{⟨\varphi ⟩\mid \varphi \text{ is a tautology}\}$ by universally selecting all assignments to the variables of $\varphi$, requiring all branches to evaluate to 1

Note that this is also in $\text{coNP}$, and any problem in $\text{coNP}$ can be easily shown to be in $\text{AP}$ by the same principle

Furthermore, $\text{AP}$ appears to be more powerful than $\text{NP}$

For example, we can solve $MIN\text{-}FORMULA$, which is thought to not be in $\text{NP}$ or $\text{coNP}$

“On input $⟨\varphi ⟩$:

1. Universally select all formulas $\psi$ that are shorter than $\varphi$
2. Existentially select an assignment to the variables of $\varphi$
3. Evaluate both $\varphi$ and $\psi$
4. Accept if the formulas evaluate to different values, otherwise reject”

This should give a clear sense of the expressive power of alternation

Alternation also allows us to establish some fascinating relationships between time and space

Theorem: For $f(n)\ge n$, $\mathrm{ATIME}(f(n))\subseteq \mathrm{SPACE}(f(n))\subseteq \mathrm{ATIME}(f^2(n))$, and for $f(n)\ge \log n$, $\mathrm{ASPACE}(f(n))=\mathrm{TIME}(2^{O(f(n))})$

As a result, $\mathrm{AL}=\mathrm{P}$, $\mathrm{AP}=\mathrm{PSPACE}$, and $\mathrm{APSPACE}=\mathrm{EXPTIME}$

We prove this as four individual $\subseteq$ relations

Lemma: For $f(n)\ge n$, $\mathrm{ATIME}(f(n))\subseteq \mathrm{SPACE}(f(n))$

We convert an alternating time machine $M$ to a deterministic machine $S$ by simulating a depth-first search on $M$‘s computation tree to determine which nodes in the tree are accepting

A naive stack (in terms of space) would store one configuration at each level

Instead, we can store only the nondeterministic choice at each level, and simply replay the computation to recover the state

Lemma: For $f(n)\ge n$, $\mathrm{SPACE}(f(n))\subseteq \mathrm{ATIME}(f^2(n))$

We use the $YIELD$ algorithm from the proof of Savitch’s Theorem, running the recursive algorithm with universal branching

The maximum time used on any branch is $O(f(n))$ to write a configuration at each level, and there are $\log 2^{df(n)}=O(f(n))$ levels, so this algorithm runs in alternating time $O(f^2(n))$

Lemma: For $f(n)\ge \log n$, we have $\mathrm{ASPACE}(f(n))\subseteq \mathrm{TIME}(2^{O(f(n))})$

The deterministic machine computes a graph of the computation of $M$ on $w$, for nodes that use at most $df(n)$ space for the appropriate constant $d$

Then the machine repeatedly scans and marks off nodes in this graph
There are $2^{O(f(n))}$ nodes in the graph, and scanning the graph that many times still takes $2^{O(f(n))}$ time

Lemma: For $f(n)\ge \log n$, we have $\mathrm{ASPACE}(f(n))\supseteq \mathrm{TIME}(2^{O(f(n))})$

We use the tableau setup described here

The tricky thing here is that our alternating machine $S$ has very little space to work with, only pointers into a tableau for the deterministic $M$ on $w$

We get around this by existentially guessing the contents of the bottom left cell, which tells us if $M$ accepts $w$

We verify our guess by existentially guessing the contents of the parents, checking whether their contents fits the transition function, and then universally verifying these guesses recursively

Hence, we never need to store more than a single pointer to a cell in the tableau, so this uses space $\log 2^{O(f(n))}=O(f(n))$

Definition: A ${\Sigma }_i$-alternating Turing machine is an alternating Turing machine that on every input and on every computation branch contains at most $i$ runs of universal or existential steps, starting with existential steps

An ${\Pi }_i$-alternating Turing machine is similar but starts with universal steps

We define ${\mathbf{\Sigma }}_i\mathbf{TIME}(f(n))$, ${\mathbf{\Pi }}_i\mathbf{TIME}(f(n))$, ${\mathbf{\Sigma }}_i\mathbf{SPACE}(f(n))$, and ${\mathbf{\Pi }}_i\mathbf{SPACE}(f(n))$ accordingly

This lets us define a more fine-grained hierarchy within $\mathrm{PSPACE}$

Definition: The polynomial time hierarchy is the collection of classes ${\mathbf{\Sigma }}_i\mathbf{P}={\bigcup }_i^{}{\Sigma }_i\mathrm{TIME}(n^k)$ and ${\mathbf{\Pi }}_k\mathbf{P}={\bigcup }_k{\Pi }_i\mathrm{TIME}(n^k)$

Definition: $\mathbf{PH}={\bigcup }_i{\Sigma }_i\mathrm{P}={\bigcup }_i{\Pi }_i\mathrm{P}$

Clearly $\mathrm{NP}={\Sigma }_1\mathrm{P}$ and $\mathrm{coNP}={\Pi }_1\mathrm{P}$
According to the algorithm we wrote out earlier, $MIN\text{-}FORMULA\in {\Pi }_2\mathrm{P}$