NEXPTIME
En théorie de la complexité, NEXPTIME, ou NEXP, est une classe de complexité, c'est-à-dire un ensemble de 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 O(2p(n)) avec certains polynômes « p »(n), et un espace mémoire illimité. C'est donc la version non-déterministe de EXPTIME.
Propriétés
D'après le théorème de hiérarchie pour le temps (en), le classe NP est différente de NEXPTIME (mais incluse)[2]. Si P = NP alors EXPTIME = NEXPTIME[3].
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[4]. On représente un graphe avec 2b sommets numérotés 0, 1, ..., 2b - 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[5].
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 Schönfinkel-Bernays est NEXPTIME-complet[5].
Jeux
Décider si une formule booléenne quantifiée avec dépendance est vraie (Dependency quantified binary formulas) est NEXPTIME-complet[6]. Par conséquent, la version en équipe de joueurs avec information imparfaite de la logique contrainte est NEXPTIME-complète également[7].
Notes et références
- (en) La classe NEXP sur le Complexity Zoo
- Article original : Joel I. Seiferas, Michael J. Fischer et Albert R. Meyer, « Separating Nondeterministic Time Complexity Classes », Journal of the ACM, vol. 25, no 1, , p. 146-167
- Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library
- Christos H. Papadimitriou et Mihalis Yannakakis, « A note on succinct representations of graphs », Information and Control, vol. 71, , p. 181–185 (DOI 10.1016/S0019-9958(86)80009-2, lire en ligne, consulté le )
- (en) Christos Papadimitriou, Computational Complexity, Addison-Wesley, (ISBN 978-0-201-53082-7)
- Gary L. Peterson et John H. Reif, « Multiple-person alternation », dans Proceedings of the 20th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, , 348–363 p. (DOI 10.1109/SFCS.1979.25, lire en ligne).
- Robert Aubrey Hearn, Games, puzzles, and computation (thèse de doctorat), (lire en ligne).