All Questions
Tagged with alternating-hierarchy cc.complexity-theory
2 questions
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
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