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).NP

Connaît-on NEXP NP ? 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 NP et un mot, est-ce qu'elle accepte?).NPNP

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 Σ 2 E X P . NEXPNPΣ2EXP
Ryan Williams

Réponses:

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 .NEXPNP

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 N E X P N P .NEXPNPNEXPNP

domotorp
la source
Vous avez soutenu bien en réponse à la réponse de Peter Shor que est probablement strictement plus puissant que N E X P . Je suis confus, cependant. Il semble que, par analogie, cela devrait signifier que N P P est plus grand que N P , bien que (je pense) ils soient égaux. Où vais-je mal ici? NEXPEXPNEXPNPPNP
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 E X P E X P ? NEXPNPNEXPEXP=NEXPEXPEXP
T ....
Le problème est que l'entrée de l'oracle est rembourrée, donc par exemple . DTIME(2n)DTIME(2n)=DTIME(22n)
domotorp
@Turbo Je ne vois pas l'erreur pour le moment mais avec cette logique, nous pourrions prouver que pour tout nous avons D T I M E ( f ( n ) ) P / p o l y , qui est un peu suspect ... Peut-être que vous devriez poser cette question. f(n)DTIME(f(n))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 P N E . Cela signifie que votre problème est Turing réductible à tout problème N E -hard. Je pense qu'il ne sait pas si cela est vrai pour tous N E X P N P .NPPNENENEXPNP

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, p o l y ( 2 n k ) = O ( 2 n k + 1 ) . Par conséquent, une autre machine N E X P devrait être capable de simuler votre machine ainsi que l'oracle.NEXPNPpoly(2nk)=O(2nk+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
NPNPNP
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