EXP-Complete Problems vs Subexponential Algorithms

Le fait qu'un problème soit EXP-temps complet implique-t-il que n'est pas en ?$A$$A$$DTIME(2^{o(n)})$

Je sais que d'après le théorème de la hiérarchie temporelle, n'est pas inclus dans . Néanmoins, cela ne semble pas exclure immédiatement l'existence d'algorithmes de temps sous-exponentiels pour chaque problème EXP-complet , car lors de la réduction d'une instance d'un problème à une instance y du problème , nous pouvons avoir un polynôme exploser en taille. En d'autres termes, .$EXP=DTIME(2^{n^{O(1)}})$$E=DTIME(2^{O(n)})$$A$$x$$B\in EXP$$A$$|y|=|x|^{O(1)}$

Ma question est donc de savoir s'il existe un argument qui exclut, sans condition, l'existence d'algorithmes temporels sous-exponentiels pour les problèmes EXP-complets.

En raison de la demande populaire, je convertis mon commentaire en réponse.

Un argument de remplissage simple montre que pour chaque constante , il existe des problèmes EXP-complete dans . En effet, corrige un problème arbitraire EXP-complet , et supposons qu'il est calculable dans le temps . Soit , et considérons le problème D'une part, est un temps polynomial réductible à via la fonction , donc est EXP-hard.$\epsilon>0$$\mathrm{DTIME}(2^{n^\epsilon})$$L$$2^{n^c}$$d>c/\epsilon$

Par contre, est calculable en temps : étant donné une entrée de taille , on vérifie d'abord (en temps polynomial) qu'elle est de la forme pour , où. On vérifie ensuite si , ce qui prend du temps .$L'$$2^{n^\epsilon}$$n$$0^m\#w$$m\ge n'^d$$n'=|w|$$w\in L$$2^{n'^c}\le2^{m^{c/d}}\le2^{m^\epsilon}\le2^{n^\epsilon}$

${}^\dagger$ En fait, la réduction telle qu'elle est donnée est même uniforme , et elle peut être rendue DLogTime si nous remplaçonsavec une limite supérieure qui est une puissance de deux.$\mathrm{AC}^0$$|w|$