Est-ce que implique ?

Est-ce que implique ? $\mathsf{EXP}=\mathsf{NEXP}$ $\mathsf{E}=\mathsf{NE}$

cc.complexity-theory conditional-results nexp structural-complexity argentpepper
la source

Oui, E = NE implique EXP = NEXP qui peut être prouvé en utilisant un argument de remplissage.

Mohammad Al-Turkistany

Il n'est pas évident pour moi pourquoi EXP = NEXP implique E = NE. Si cela était vrai, alors tout algorithme à pour Succinct3SAT peut être converti en algorithme à pour Succinct3SAT. Peut-être que vous avez inversé les choses et que vous vouliez poser des questions sur l'autre implication?

2^{n^{k}}

$2^{n^k}$

2^{O (n)}

$2^{O(n)}$

Ryan Williams

Et puis P = NP si P = 0 ou N = 1!

Daniel Apon

Oui. Je suppose que c'est un problème de devoirs.

Mohammad Al-Turkistany

Je ne comprends pas la fermeture de cette question comme «pas une vraie question» après qu'elle a été modifiée en une question raisonnable (bien que le libellé de la question ne soit pas intéressant). Par exemple, le commentaire de Ryan Williams peut être une réponse.

Tsuyoshi Ito

Réponses:

Pour autant que je sache, c'est ouvert. Cela peut être prouvable (car son hypothèse peut être fausse) ou il est tout simplement difficile de montrer que tout algorithme à heures pour Succinct3SAT peut être converti en un algorithme à heures pour Succinct3SAT. $2^{n^k}$ $2^{O(n)}$

En général, les théorèmes de ce type sont appelés "effondrements vers le bas" qui disent que si deux "grandes" classes sont égales, alors deux "petites" classes sont égales. Ces théorèmes sont rares. Habituellement, vous pouvez soit prouver un "effondrement vers le haut" (de petites classes égales implique des classes plus grandes égales, comme implique ) ou son contrapositif, une "séparation vers le bas". $P = NP$ $NEXP = EXP$

Quelque chose dans le sens de ce que vous voulez est le théorème de Hartmanis, Immerman et Sewelson ( http://dl.acm.org/citation.cfm?id=808769 ) selon lequel chaque ensemble clairsemé de est contenu dans . Cela donne un "effondrement vers le bas" mais uniquement pour les ensembles clairsemés (ces ensembles qui ne contiennent que des chaînes de longueur ). $NE = E$ $\iff$ $NP$ $P$ $poly(n)$ $n$

Ryan Williams
la source