EXP-Complete Problems vs Subexponential Algorithms

10

Le fait qu'un problème soit EXP-temps complet implique-t-il que n'est pas en ?AADTIME(2o(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(2nO(1))E=DTIME(2O(n))AxBEXPA|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.

vérification
la source
11
Au contraire, un argument de remplissage trivial montre que pour chaque , il existe des problèmes EXP-complete calculables dans le temps . ϵ>02nϵ
Emil Jeřábek du
7
@ EmilJeřábek Merci. Je suppose que votre commentaire est la réponse que je cherchais. Pourriez-vous s'il vous plaît le développer en une réponse?
vérification du

Réponses:

12

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.ϵ>0DTIME(2nϵ)L2ncd>c/ϵ

L={0m#w:wL,m|w|d}.
LLw0|w|d#wL

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 .L2nϵn0m#wmndn=|w|wL2nc2mc/d2mϵ2nϵ


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.AC0|w|

Emil Jeřábek
la source