Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

1
vote
0answers
170 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 ...
-1
votes
1answer
118 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 ...
8
votes
0answers
143 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)}$ ...
9
votes
1answer
172 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 ...
15
votes
3answers
420 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 \...