Questions tagged [alternating-hierarchy]
The alternating-hierarchy tag has no usage guidance.
2 questions with no upvoted or accepted answers
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
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