Questions tagged [alternation]
The alternation tag has no usage guidance.
6
questions
3
votes
0
answers
107
views
State-based vs. transition-based definitions of alternating automata
Maybe this is a naïve question but I'm having difficulties finding the answer in the literature.
Alternating finite automata (AFA) are usually defined in modern literature in the following terms. An ...
- 1,588
2
votes
0
answers
608
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
250
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
202
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)}$ ...
- 27.3k
9
votes
2
answers
260
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.5k
14
votes
3
answers
577
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.5k