Questions tagged [alternation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 \...
user avatar
  • 21.3k