Preguntas etiquetadas con alternation

Aceleración no determinista del cálculo determinista

¿Puede el no determinismo acelerar el cálculo determinista? Si es así, ¿cuánto? Al acelerar el cálculo determinista por el no determinismo me refiero a los resultados de la forma: DTime(f(n))⊆NTime(n)DTime(f(n))⊆NTime(n)\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n) Por ejemplo, algo...

¿Es plausible una aceleración del no determinismo cuadrático de la computación determinista?

Este es un seguimiento de la aceleración no determinista del cálculo determinista . ¿Es plausible que el no determinismo (o una alternancia más general) permitiría una aceleración cuadrática general de la computación determinista? ¿O hay consecuencias inverosímiles conocidas para algo como...