Questions tagged [alternating-hierarchy]
The alternating-hierarchy tag has no usage guidance.
4 questions
2
votes
0
answers
626
views
Relationship of the P=PSPACE problem to alternating complexity classes
From a very naive point of view of someone who haven't studied complexity theory in depth, I am wondering whether the theorems that APSPACE=EXPTIME and AP=PSPACE have any derived results on separating ...
- 21
8
votes
1
answer
1k
views
canonical complete problems for $\Delta^P_n$
Finding whether or not a QBF can be satisfied is a canonical complete problem for both $\Sigma^P_n$ (start from $\exists$) and $\Pi^P_n$ (start from $\forall$). What is the canonical complete problem ...
- 183
10
votes
0
answers
365
views
Collapsing of exptime and alternation bounded turing machine
This question was already asked on math overflow, but I did not find any answer to my question (or let say the answer was that up to the knowledge of those people, no answer were known)
Let C be a ...
- 1,561
14
votes
2
answers
1k
views
Space alternating hierarchy
It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions).
In the same paper, Immerman state that the ...
- 1,561