HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why is my trivial reasoning for $PSPACE = PH$ wrong?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
reasoningwhypspacetrivialforwrong

Problem

If $\sum_i^p$ denotes $ith$ polynomial hierarchy. And $\sum_i TIME( T(n) )$ denotes set of languages accepted by $T(n)$ time alternating Turing machine $M$ whose initial state is labeled $\exists$ and sequence of choices leads $M$ to change at most $i-1$ times from states with one label to another.

Then I know $\sum_i^p= \cup_c\sum_i Time ( n^c)$. Then by taking summation on $i$ both sides we get $PH=\cup_i \sum_i^p=\cup_i\cup_c \sum_i TIME(n^c)=\cup_c\cup_i \sum_i TIME(n^c)=\cup_c \sum_i TIME(n^c)=\cup_c \ TIME(n^c)=AP=PSPACE$
where $AP=\cup_c ATIME(n^c)$ ie. set of languages having polynomial runtime using an alternating Turing machine.

Thus we get $PH=PSPACE$, which I know does not have a proof. I am misunderstanding something trivial, but cant figure out what ?

Solution

Alternating polynomial time allows for an unbounded number of alternations. In contrast, every level of the polynomial hierarchy only allows for a fixed number of alternations. Therefore your argument only shows that $\mathsf{PH} \subseteq \mathsf{AP}=\mathsf{PSPACE}$.

Context

StackExchange Computer Science Q#53772, answer score: 6

Revisions (0)

No revisions yet.