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(2^p(n)) avec certains polynômes « 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^[1] :

${\displaystyle {\mbox{NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}(2^{n^{k}})}$.

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 2^b sommets numérotés 0, 1, ..., 2^b - 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

1. (en) La classe NEXP sur le Complexity Zoo
2. Article original : Joel I. Seiferas, Michael J. Fischer et Albert R. Meyer, « Separating Nondeterministic Time Complexity Classes », Journal of the ACM, vol. 25, n^o 1,‎ 1978, p. 146-167
3. 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
4. Christos H. Papadimitriou et Mihalis Yannakakis, « A note on succinct representations of graphs », Information and Control, vol. 71,‎ 1^er décembre 1986, p. 181–185 (DOI 10.1016/S0019-9958(86)80009-2, lire en ligne, consulté le 18 octobre 2016)
5. (en) Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1993 (ISBN 978-0-201-53082-7)
6. 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, 29 octobre 1979, 348–363 p. (DOI 10.1109/SFCS.1979.25, lire en ligne).
7. Robert Aubrey Hearn, Games, puzzles, and computation (thèse de doctorat), 1^er janvier 2006 (lire en ligne).

Lien externe

• (en) La classe NEXP sur le Complexity Zoo

• Portail de l'informatique théorique