Skip to main content

Questions tagged [alternating-hierarchy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers
619 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 ...
user519216's user avatar
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 ...
kvaruni's user avatar
  • 183
10 votes
0 answers
363 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 ...
Arthur MILCHIOR's user avatar
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 ...
Arthur MILCHIOR's user avatar