Voir la source de NEXPTIME

En [[théorie de la complexité (informatique théorique)|théorie de la complexité]], '''NEXPTIME''', ou '''NEXP''', est une classe de complexité, c'est-à-dire un ensemble de [[problème de décision|problèmes de décision]]. 

Plus précisément, c'est l'ensemble des problèmes de décision qui peuvent se résoudre sur une [[machine de Turing non déterministe]] en temps [[Notation O|O]](2<sup>''p''(n)</sup>) avec certains [[polynôme]]s « p »(n), et un espace mémoire illimité. C'est donc la version non-déterministe de [[EXPTIME]].

== Définition ==
En termes de [[NTIME]], la classe est définie par<ref>{{Complexity Zoo|fin=N#nexp|nom=NEXP}}</ref> :

:<math>\mbox{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(2^{n^k})</math>.

== Propriétés ==

D'après le {{lien|trad=Time hierarchy theorem|fr=théorème de hiérarchie pour le temps}}, le classe [[NP (complexité)|NP]] est différente de NEXPTIME (mais incluse)<ref>Article original : 
{{article
 |auteur1 = Joel I. Seiferas
 |auteur2 = Michael J. Fischer
 |auteur3 = Albert R. Meyer
 |titre     = Separating Nondeterministic Time Complexity Classes
 |périodique  = [[Journal of the ACM]]
 |volume    = 25 |numéro    = 1 | passage     = 146-167
 |année    = 1978}}</ref>. Si P = NP alors EXPTIME = NEXPTIME<ref>Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. ''Information and Control'', volume 65, issue 2/3, pp.158&#x2013;181. 1985. [http://portal.acm.org/citation.cfm?id=808769 At ACM Digital Library]</ref>.

== Problème NEXPTIME-complet ==
Un problème est NEXPTIME-dur si tout problème de NEXPTIME s'y réduit en temps polynomial. Un problème est NEXPTIME-complet s'il est dans NEXPTIME et s'il est NEXPTIME-dur.

=== Problèmes NEXPTIME-complets obtenus par concision ===
On peut transformer un [[problème NP-complet]] en un problème NEXPTIME-complet si on rend l'entrée du problème plus concise. Par exemple, le problème de trouver un chemin hamiltonien dans un graphe représenté par une [[matrice d'adjacence]] est NP-complet. Le même problème où le graphe est représenté de manière concise par un circuit concis est NEXPTIME-complet<ref>{{Article|prénom1=Christos H.|nom1=Papadimitriou|prénom2=Mihalis|nom2=Yannakakis|titre=A note on succinct representations of graphs|périodique=Information and Control|volume=71|date=1986-12-01|doi=10.1016/S0019-9958(86)80009-2|lire en ligne=http://www.sciencedirect.com/science/article/pii/S0019995886800092|consulté le=2016-10-18|pages=181–185}}</ref>. On représente un graphe avec 2<sup>b</sup> sommets numérotés 0, 1, ..., 2<sup>b</sup> - 1 par un [[circuit booléen]] avec 2b entrées et tel qu'il y a un arc du sommet i au sommet j si le circuit booléen accepte les représentations binaires des nombres i et j. Ainsi, la version succincte du problème du chemin hamiltonien se reformule ainsi : étant donné un circuit booléen C, est-ce que le graphe correspondant à C contient un chemin hamiltonien<ref name=":0">{{Computational Complexity (Papadimitriou)}}</ref>.

Plusieurs problèmes de décision avec une version concise sont NEXPTIME-complets :
* Coupe maximale dans un graphe représenté par un circuit booléen
* 3SAT concis
* SAT concis
* SAT d'un circuit booléen représenté de manière concise

=== Logique du premier ordre ===
Le problème de satisfiabilité de la [[Classe de Bernays-Schönfinkel|classe de Schönfinkel-Bernays]] est NEXPTIME-complet<ref name=":0" />.

=== Jeux ===
Décider si une formule booléenne quantifiée avec dépendance est vraie (''{{langue|en|Dependency quantified binary formulas}}'') est NEXPTIME-complet<ref>{{Chapitre|prénom1=Gary L.|nom1=Peterson|prénom2=John H.|nom2=Reif|titre=Multiple-person alternation|titre ouvrage=Proceedings of the 20th Annual Symposium on Foundations of Computer Science|éditeur=IEEE Computer Society|date=1979-10-29|doi=10.1109/SFCS.1979.25|lire en ligne=http://dl.acm.org/citation.cfm?id=1382433.1382634|consulté le=2018-04-26|pages=348–363}}.</ref>. Par conséquent, la version en équipe de joueurs avec information imparfaite de la [[logique contrainte]] est NEXPTIME-complète également<ref>{{Ouvrage|prénom1=Robert Aubrey|nom1=Hearn|titre=Games, puzzles, and computation|date=2006-01-01|lire en ligne=http://dl.acm.org/citation.cfm?id=1269411|consulté le=2018-04-28|nature ouvrage=thèse de doctorat}}.</ref>.

== Notes et références ==
<references />

== Lien externe ==
* {{Complexity Zoo|fin=N#nexp|nom=NEXP}}

{{Palette|Théorie de la complexité}}

{{Portail|informatique théorique}}

[[Catégorie:Classe de complexité]]