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.

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

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

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

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.

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

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

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

• (en) La classe NEXP sur le Complexity Zoo

• Portail de l'informatique théorique