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

14

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)

Par exemple quelque chose comme

DTime(n2)NTime(n)

Quel est le résultat d'accélération le plus connu du calcul déterministe par non-déterminisme? Que dire ΣkPTime(n) ou encore ATime(n) à la place de NTjeme(n) ?

Supposons que les classes de complexité soient définies à l'aide de machines de Turing à bandes multiples pour éviter les particularités bien connues des machines de Turing à bande sub-quadratique temporelle.

Kaveh
la source
3
(Par le théorème 4.1 et le temps de la hiérarchie Théorème, votre exemple ne peut pas tenir pour 1-bande mémoires de traduction.)

Réponses:

11

Vous ne devez pas vous attendre à une accélération excitante. Nous avons

DTIME(f(n))NTIME(f(n))ATIME(f(n))DSPACE(f(n)),

et la simulation la plus connue du temps déterministe par l'espace est toujours le théorème de Hopcroft – Paul – Valiant

DTIME(f(n))DSPACE(f(n)/logf(n)).

Ainsi, le non-déterminisme ou l'alternance n'est pas connu pour donner une accélération de plus d'un facteur logarithmique. (Je soupçonne qu'aucune accélération super-linéaire n'est connue non plus, bien que je ne sois pas sûr que le théorème du HPV ne puisse pas fonctionner avec ATIME à la place de DSPACE.)

Emil Jeřábek soutient Monica
la source
1
Pour les machines de Turing en ligne à bande unique, c'est le folklore que . NTIME(n)DSPACE(n)
Michael Wehar
1
Pour les machines de Turing à deux bandes, nous avons comme indiqué ci-dessus. DTIME(n)DSPACE(n/log(n))
Michael Wehar
2
La question concerne les machines de Turing multitape.
Emil Jeřábek soutient Monica le
4
Je voulais juste apporter des éclaircissements supplémentaires au lecteur intéressé.
Michael Wehar
2
Par Paul-Pippenger-Szemerédi-Trotter, la première inclusion est pour le cas spécial où f ( n ) = n . DTIME(f(n))NTIME(f(n))f(n)=n
András Salamon
6

Il existe deux concepts distincts:

(1) Simulation efficace de machines déterministes par des machines non déterministes.

(2) Accélération des résultats qui sont obtenus en appliquant une simulation encore et encore.

Je ne connais aucune simulation efficace de machines déterministes par des machines non déterministes, mais je connais plusieurs résultats d'accélération qui pourraient être utilisés s'il existe des simulations efficaces.

Considérons la classe des langages qui sont décidables par une machine de Turing non déterministe fonctionnant pendant t ( n ) temps en utilisant seulement g ( n ) suppositions non déterministes. En d'autres termes, la longueur du témoin est limitée par g ( n ) .NTIGU(t(n),g(n))t(n)g(n)g(n)

Si vous avez une simulation plus efficace utilisant uniquement suppositions non déterministes log ( n ) , alors je pense que vous pouvez l'accélérer un peu. En particulier, je pense que vous pouvez prouver ce qui suit:log(n)

Si , alors D T I M E ( 2 DTIME(nlog(n))NTIGU(n,log(n)).DTIME(2n)NTIME(n)

Si vous trouvez cela intéressant, je peux rédiger la preuve.

Ryan Williams a présenté quelques accélérations connexes dans «L'amélioration de la recherche exhaustive implique des limites inférieures superpolynomiales».

Michael Wehar
la source
1
Comme vous pouvez le voir, est une hypothèse assez grande et il est tout à fait raisonnable que vous puissiez prouver que l'hypothèse est fausse . Faites-moi savoir si vous le faites. :)DTIME(nlog(n))NTIGU(n,log(n))
Michael Wehar
@AndrasSalamon: Comment cela découle-t-il d'une recherche exhaustive?
@RickyDemer vous avez raison, ce n'est pas le cas; ont supprimé les commentaires. Je supposais implicitement que le non-déterminisme était à la fin du calcul, mais il devrait être supposé être au début.
András Salamon
Mise à jour: enfin commencé à rédiger le résultat d'accélération proposé que j'ai mentionné. Cela semble être un peu différent des autres résultats d'accélération que j'ai trouvés. N'hésitez pas à me répondre ou à m'envoyer un e-mail si vous souhaitez en discuter. Je vous remercie! :)
Michael Wehar
1
serait certainement jeter un oeil, il s'agit d'une approche intrigante.
András Salamon
6

Voici une explication des raisons pour lesquelles une accélération non déterministe de la quartique générale du calcul déterministe, même si elle est vraie, serait difficile à prouver:

Supposons qu'une accélération quartique non déterministe générale du calcul déterministe comme vérifiée. Dans un souci de contradiction, supposons que S A TD T i m e ( o ( n 2 / lg n ) ) . Il y a une réduction du temps quadratique de tout problème dans N T i m e ( nDTime(n4)NTime(n)SATDTime(o(n2/lgn))NTime(n) à . En les combinant, nous aurions D T i mSAT contredisant le théorème de la hiérarchie temporelle.DTime(n4)DTime(o(n4/lgn))

Par conséquent, une accélération non terminique quartique générale du calcul déterministe impliquerait une borne inférieure pour :SAT

DTime(n4)NTime(n)SATDTime(o(n2/lgn))

SAT

f(n)

DTime(f(n2))NTime(n)SATDTime(o(f(n)/lgn)).

(If in place of SAT we pick a problem which is hard for NTime(n) under linear-time reductions then this would give f(n)/lgn lower bound for that problem. If we fix the number of the machine tapes to some k2 then we can use Fürer's time hierarchy theorem which does not have the lgn factor.)

Kaveh
la source
Since we don't even know that SAT is not in DTime(n), we don't know an ω(nlgn)2 speed-up.
Kaveh