Classe de complexité NEXP

11

J'ai un problème qui se trouve dans NEXP et peut également être résolu par une MT alternative utilisant le temps exponentiel et une seule alternance (commençant dans un état existentiel). $^{\text{NP}}$

Connaît-on NEXP ? Est-il égal à NEXP ou à une autre classe? Y a-t-il des problèmes complets autres que génériques (étant donné une machine NEXP et un mot, est-ce qu'elle accepte?). $^{\text{NP}}$ $^{\text{NP}}$

cc.complexity-theory reference-request complexity-classes nexp Hsien-Chih Chang 張顯之
la source

2

Découvrez les travaux sur la hiérarchie temporelle exponentielle, par exemple ecommons.library.cornell.edu/bitstream/1813/6617/1/86-777.pdf

5501

3

Notez que

n'ont un autre nom dans la littérature (basée sur la caractérisation de l' alternance), à savoir

.

N E X P^{N P}

$NEXP^{NP}$

Σ_{2} E X P

$\Sigma_2 EXP$

Ryan Williams

7

Un problème naturel complet consiste à décider une phrase de l'arithmétique de Presburger avec un préfixe de quantificateur (comme illustré ici ). D'autres problèmes complets liés à la théorie des bases de données ont été étudiés ici . $\text{NEXP}^{\text{NP}}$ $\exists^*\forall^*\exists^*$

Christoph Haase
la source

5

est (probablement) plus grand que NEXP, car nous pouvons poser des questions de longueur exponentielle depuis l'oracle. Ce NP dans la puissance est pratiquement un NEXP là-bas, donc par exemple. co-NEXP est contenu dans . $NEXP^{NP}$ $NEXP^{NP}$

domotorp
la source

Vous avez soutenu bien en réponse à la réponse de Peter Shor que

est probablement strictement plus puissant que

. Je suis confus, cependant. Il semble que, par analogie, cela devrait signifier que

est plus grand que

, bien que (je pense) ils soient égaux. Où vais-je mal ici?

N E X P^{E X P}

$NEXP^{EXP}$

N E X P

$NEXP$

N P^{P}

$NP^P$

N P

$NP$

Huck Bennett

7

@Huck Les polynômes sont fermés sous les polynômes. Les exponentielles ne le sont pas. Donc, je peux alimenter l'oracle EXP un argument exponentiellement long, et il peut faire un travail exponentiel dans cet argument, qui est doublement exponentiel dans le problème d'origine.

Mark Reitblatt

@domotorp Je pensais que

? Et

?

N E X P^{N P} \subseteq N E X P^{E X P} = N E X P

$NEXP^{NP}\subseteq NEXP^{EXP}=NEXP$

E X P^{E X P}

$EXP^{EXP}$

T ....

Le problème est que l'entrée de l'oracle est rembourrée, donc par exemple

.

D T I M E (2^{n})^{D T I M E (2^{n})} = D T I M E (2^{2^{n}})

$DTIME(2^n)^{DTIME(2^n)}=DTIME(2^{2^{n}})$

domotorp

@Turbo Je ne vois pas l'erreur pour le moment mais avec cette logique, nous pourrions prouver que pour tout

nous avons

, qui est un peu suspect ... Peut-être que vous devriez poser cette question.

f (n)

$f(n)$

D T I M E (f (n)) \subset P / p o l y

$DTIME(f(n))\subset P/poly$

domotorp

3

L' expansion de mon commentaire ci - dessus un peu: Si vous avez une seule requête à la -oracle (comme dans votre cas), il fait suite aux travaux de Hemaspaandra, que votre problème est dans . Cela signifie que votre problème est Turing réductible à tout problème -hard. Je pense qu'il ne sait pas si cela est vrai pour tous . $NP$ $P^{NE}$ $NE$ $NEXP^{NP}$

5501
la source

1

La plus grande requête qu'une machine puisse faire à l'oracle est exponentielle dans la longueur de l'entrée. La puissance de l'oracle n'est que polynomiale en cela, qui devrait également être exponentielle. En d'autres termes, . Par conséquent, une autre machine devrait être capable de simuler votre machine ainsi que l'oracle. $NEXP^{NP}$ $poly(2^{n^k})=O(2^{n^{k+1}})$ $NEXP$

Modifié pour les parenthèses ...

Aubrey da Cunha
la source

3

Les MNT ne fonctionnent pas tout à fait comme ça. Les MNT se divisent et si une copie accepte, le tout accepte. Lorsque vous vous séparez, vous ne pouvez pas regarder les résultats de vos copies non dét. Donc, si je faisais une requête sur une machine NP et que je retournais immédiatement la réponse opposée, comment simuleriez-vous cela?

Mark Reitblatt

1

N P^{N P}

$NP^{NP}$

N P

$NP$

Ah oui. Lors de la simulation d'une requête Oracle, si le résultat correct est non, toutes les branches renverront non. D'un autre côté, si le résultat correct est oui, alors au moins une branche retournera oui. En particulier, certains peuvent retourner non. Ainsi, lorsque @Mark le suggère, vous annulez le résultat de la requête, vous risquez d'obtenir des faux positifs.

Aubrey da Cunha

Classe de complexité NEXP

Réponses: