NEXPTIME

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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ôme "p"(n), et un espace mémoire illimité. C'est donc la version non-déterministe de EXPTIME.

Définition[modifier | modifier le code]

En termes de NTIME, la classe est définie par [1] :

.

Propriétés[modifier | modifier le code]

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

Problème NEXPTIME-complet[modifier | modifier le code]

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[modifier | modifier le code]

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[3]. 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[4].

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[modifier | modifier le code]

Le problème de satisfiabilité de la classe de Schönfinkel-Bernays est NEXPTIME-complet[4].

Notes et références[modifier | modifier le code]

  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, no 1,‎ , p. 146-167
  3. 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)
  4. a et b (en) Christos Papadimitriou, Computational Complexity, Addison-Wesley, (ISBN 978-0-201-53082-7)

Lien externe[modifier | modifier le code]