À quelle vitesse un algorithme non déterministe pour un problème EXPTIME complet devrait-il impliquer

À quelle vitesse un algorithme non déterministe pour un problème EXPTIME complet devrait-il impliquer $P \neq NP$ ? Un temps polynomial algorithme non déterministe impliquerait immédiatement parce que $P \neq EXPTIME$ mais personne ne croit $NP = EXPTIME$ . Si j'ai fait l'algèbre à droite (voir ci-dessous), le théorème de la hiérarchie temporelle donnerait toujours l' implication $P \neq NP$ pour $O(2^n/f(n))$ temps d'exécution pour tout superpolynôme $f(\cdot)$ , mais pour tout ce que je sais, il y a des problèmes complets avec des réductions efficaces qui permettent à des algorithmes plus lents de donner le résultat. Y a-t-il des problèmes EXPTIME-complet où nous savons que quelque chose comme $2^n/n$ ou $2^n/n^2$ avec un non-déterminisme est suffisant?

Clarification de "l'algèbre": $P = NP$ implique $EXPTIME=NEXPTIME$ par un argument de remplissage, donc un algorithme non déterministe $2^n/f(n)$ pour un problème EXPTIME complet serait également un pour un problème NEXPTIME complet. Pour le superpolynôme $f(\cdot)$ cela contredirait le théorème de la hiérarchie temporelle non déterministe puisque nous pourrions réduire en utilisant $L \in$ NTIME $(2^n)$ .

cc.complexity-theory Anonyme
la source

Je pense que vous avez réellement besoin du temps d'exécution

2no(1) $2^{n^{o(1)}}$ pour obtenir une contradiction du théorème de la hiérarchie temporelle. Je pense aussi que cela semble assez improbable.

Sasho Nikolov

Juste pour reformuler la question: quel est le plus grand

f $f$ où ExpTime

⊆ $\subseteq$ NTime

(f(n)) $(f(n))$ implique NP

⊈ $\not\subseteq$ P?

Kaveh

ps: si vous enregistrez un compte, vous pouvez modifier votre question plus facilement.

Kaveh

Je crois que Sasho est correct, si

tel que

est

-complet et

est

-complete et est réductible à dans le temps , alors il est toujours possible queEXPTIME=NEXPTIME $EXPTIME=NEXPTIME$

L $L$

EXPTIME $EXPTIME$

L′ $L'$

NEXPTIME $NEXPTIME$

L′ $L'$

L $L$

O(nk) $O(n^k)$

L∈NTIME(2n√k) $L \in NTIME(2^{\sqrt[k]{n}})$ sans aucune contradiction car l'instance de peut être plus grande que .

L $L$

O(nk) $O(n^k)$

L′ $L'$

Joe Bebel

Réponses:

Je pense que c'est plus facile de le retourner.

Si , alors pour une constante , et tout . Puisque ne contient pas , cela signifie que nous ne pouvons pas résoudre, disons tous les problèmes dans dans $\mathsf{P}=\mathsf{NP}$ $\mathsf{NTIME}(T(n)) \subset \mathsf{DTIME} ((T(n))^c)$ $c$ $T(n) > n$ $\mathsf{DTIME} ((T(n)^c)$ $\mathsf{DTIME}(T(n)^{c}\log T(n)) \subset \mathsf{DTIME}(T(n)^{c+1})$ $\mathsf{DTIME}(2^n)$ $\mathsf{NTIME} (2^{\epsilon n})$ pour certains . Donc, un algorithme non déterministe à temps pour un problème complet pour sous des réductions quasi linéaires serait suffisant pour prouver . $\epsilon$ $2^{o(n)}$ $\mathsf{DTIME} (2^n)$ $\mathsf{P} \neq \mathsf{NP}$

Russell Impagliazzo
la source

Merci d'avoir pris le temps de fournir une explication des raisons pour lesquelles brève

implique

. DTIME(2n)⊆NTIME(2o(n)) $DTIME(2^n) \subseteq NTIME(2^{o(n)})$

P≠NP $P \neq NP$

Michael Wehar

Et, merci d'avoir souligné que le théorème de la hiérarchie temporelle déterministe ou non déterministe pourrait être utilisé. :)

Michael Wehar

Réponse simple: pour chaque problème - , il existe une constante telle que si nous pouvions résoudre le problème dans $EXPTIME$ $hard$ $c$ , puis. $NTIME(2^{o(n^{\frac{1}{c}})})$ $P \neq NP$

Remarque: La constante provient des explosions de taille d'instance qui résultent des réductions. $c$

Justification: Soit un problème - . Cela signifie que chaque problème dans est réductibles polynomiale à . En fait, nous pouvons en montrer plus. $X$ $EXPTIME$ $hard$ $EXPTIME$ $X$

Le problème d'acceptation pour les temps borné machines de Turing déterministes est en et est donc réductible en temps polynomial à . $2^n$ $DTIME(n \cdot 2^n) \subseteq EXPTIME$ $X$

Par conséquent, il doit y avoir une constante fixe telle que chaque problème dans est un temps polynomial réductible à où la taille de l'instance est de . Autrement dit, les instances de taille n sont réduits en cas de taille pour . $c$ $DTIME(2^n)$ $X$ $O(n^c)$ $O(n^c)$ $X$

Maintenant, si nous avions , puis. Cependant, cela implique(voir ci-dessous pour plus de détails). $X \in NTIME(2^{o(n^{\frac{1}{c}})})$ $DTIME(2^n) \subseteq NTIME(2^{o(n)})$ $P \neq NP$

Détails supplémentaires: On peut montrer que . $P=NP$ $\Leftrightarrow$ $\exists c^{\prime}$ $\forall k$ $NTIME(n^k) \subseteq DTIME(n^{c^{\prime}k})$

En d' autres termes, si vous pouvez résoudre un - problème en temps polynomial, alors il existe un moyen uniforme d'accélérer un problème dans . $NP$ $complete$ $NP$

Maintenant, supposons que . Par le précédent (avec = 1) on obtient une constante telle que $P=NP$ $k$ $c^{\prime}$

$NTIME(n) \subseteq DTIME(n^{c^{\prime}}).$

Ensuite, nous pouvons utiliser le remplissage pour augmenter cette inclusion et obtenir

$NTIME(2^{n}) \subseteq DTIME(2^{c^{\prime}n}).$

Ensuite, par le théorème de la hiérarchie temporelle déterministe, nous avons pour tout .

$NTIME(2^{n}) \subseteq DTIME(2^{c^{\prime}n}) \subsetneq DTIME(2^{(c^{\prime}+\epsilon)n})$

$\epsilon > 0$

Par conséquent, nous ne pouvions pas avoir $DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{n}).$

De plus, nous ne pouvions pas avoir parce que par remplissage, nous obtiendrions . $DTIME(2^{n}) \subseteq NTIME(2^{o(n)})$ $DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{o(n)})$

Autre question: Quelqu'un a-t-il des exemples simples de problèmes - où nous pouvons facilement déterminer la constante de gonflement de la taille de l'instance ? $EXPTIME$ $complete$ $c$

Michael Wehar
la source

Le problème d'acceptation pour

est lui - même

-complete, qui est, le langage

consistant en DTM

que sur l' entrée

accepter dans les

, car chaque langue

a une $DTIME(2^n)$

$EXPTIME$

$L = \{\langle T, x, 1^m \rangle\}$

$T$

$x$

$2^m$

$L' \in EXPTIME$

$T$ that accepts

$x \in L'$ in time

$2^{O(|x|^k)})$ for some

$k$ , so that proper choice of

$m = O(|x|^k)$ reduces

$L'$ to

$L$ . In particular the constant (

$c=1$ ) then seems to show that the speedup (that is,

$f(n)$ ) must be exponential if to show

$P \ne NP$ , if you choose this particular

$EXPTIME$ -complete language.

Joe Bebel

@JoeBebel Hi Joe, thanks for the comment. I think it's valuable that you further considered this problem

$L$ . Here, we can say more than just

$L \in NTIME(2^{o(n)})$ implies

$P \neq NP$ . For this particular artificial problem

$L$ , we may be able to say something like for any

$k$ ,

$L \in NTIME(2^{\frac{n}{k}})$ implies

$NTIME(n) \nsubseteq DTIME(n^{k-\epsilon})$ for all

$\epsilon > 0$ .

Michael Wehar