I'm trying to figure out this question:

Let's say we have an alternating Turing Machine that makes a restricted number of alternations (i.e. switches from a universal to an existential state or vice versa) that works in polynomial space.

Prove that we can simulate that machine by a deterministic machine also working in polynomial space.

Could some give me a hint how to approach this problem?


I was recently thinking about similar problem. After literature reserch I found out that

for every $S(n)\geq \log(n)$ hierarchy of $k-altBounded-ASpace((S(n)))$ colapses to $1-altBounded-ASpace((S(n)))=NSpace(S(n))$. I found it in article "Viliam Geffert A Hierarchy that does not collapse: alternations in low space". to convert to PSpace you can use Savitch's theorem.

But I can show you scatch of my simulation. (for simplicity let's assume that $S(n) \geq n$)

1) due to Immerman-Szelepczényi theorem: $USPACE(S(n))= NSPACE(S(n))$, where U-TM is using only universal branching.

2) let $L_{M,Q}=\{C| C$ is configuration M, subtree under configuration $C$ is accepting and consist only from $Q$-konfigurations}. Where $Q \in \{\forall,\exists\}$ Then $L_{M,Q} \in xSPACE(S(n))$, where $x \in\{N,U\}$ is coresponding to $Q$. We only need to simulate original ATM from $C$. So also $L_{M,Q} \in \overline{x}SPACE(S(n))$ where $\overline{x}$ is oposite to $x$.(due to first statment)

3) We will simulate S(n) space bounded ATM $M$ by onother ATM $N$ using k-1 alternations. During first k-1 alternations $N$ is simulationg $M$. Then in configucation $C$, which $C$ reqires k-th alternation we will stop simulation and write $C$ on working tape. Then we will run machine $X$ for $L_{M,Q}$ on $C$. This machine $X$ has same type as our current alternation, so we don't have to make k-th alternation. $X$ is working in $S(n)$ space.

So we saved one alternation. Ssing this simulation k-times we will get NTM. On NTM we will use Savitch's theorem. so

$k-altBounded-ASpace((S(n))) = 1-altBounded-ASpace((S(n))) = NSPACE(S(n)) = DSPACE(S(n)^2)$

I hope that hepls:) And sorry for my english.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.