Questions marquées «alternation»

Accélération non déterministe du calcul déterministe

Le non-déterminisme peut-il accélérer le calcul déterministe? Si oui, combien? En accélérant le calcul déterministe par le non-déterminisme, j'entends les résultats de la forme: DTime(f(n))⊆NTime(n)DTime(f(n))⊆NTime(n)\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n) Par exemple quelque chose comme...

Une accélération quadratique du non-déterminisme du calcul déterministe est-elle plausible?

Il s'agit d'un suivi de l'accélération non déterministe du calcul déterministe . Est-il plausible que le non-déterminisme (ou plus généralement l'alternance) permette une accélération quadratique générale du calcul déterministe? Ou y a-t-il des conséquences invraisemblables connues pour quelque...