Questions tagged [alternation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
0 answers

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 ...
Nicola Gigante's user avatar
2 votes
0 answers

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
-1 votes
1 answer

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 ...
springer77's user avatar
7 votes
0 answers

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)}$ ...
Ryan Williams's user avatar
9 votes
2 answers

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 ...
Kaveh's user avatar
  • 21.5k
14 votes
3 answers

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 \...
Kaveh's user avatar
  • 21.5k