Questions tagged [alternation]
The alternation tag has no usage guidance.
5
questions
2
votes
0
answers
591
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
-1
votes
1
answer
230
views
polylogarithmic space [closed]
I apologize if this is a silly question, but could someone tell me whether the class polyL (polylogarithmic space) is equal to the class ATIME(polylog)? If so, where can I find a reference to this or ...
7
votes
0
answers
190
views
Oracles for sub-exponential circuit complexity of $\Sigma_2 EXP$
Couldn't find this one anywhere...
It's an open problem whether $\Sigma_2 EXP$ problems have exponential-size circuit complexity. Is there an oracle relative to which $\Sigma_2 EXP$ has $2^{o(n)}$ ...
- 26.4k
9
votes
1
answer
207
views
Is a quadratic nondeterminism speed-up of deterministic computation plausible?
This is a follow up to
nondeterministic speed-up of deterministic computation.
Is it plausible that nondeterminism (or more generally alternation)
would allow a general quadratic speed-up of ...
- 21.3k
14
votes
3
answers
539
views
Nondeterministic speed-up of deterministic computation
Can nondeterminism speed-up deterministic computation? If yes, how much?
By speeding-up deterministic computation by nondeterminism I mean results of the form:
$\mathsf{DTime}(f(n)) \subseteq \...
- 21.3k