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)) où p(n) est un polynôme. C'est donc la version non-déterministe de EXPTIME.

Définition En termes de NTIME, la classe est définie par :

. Comme la classe NP, on peut aussi définir NEXPTIME en utilisant un vérificateur. Un problème A est dans NEXPTIME s'il existe des polynômes p et q, et une machine de Turing M déterministe (le vérificateur), tel que :

Pour toute instance x et tout mot y, M sur (x, y) s'exécute en temps 2p(|x|) Pour toute instance x, l'instance x est positive pour A ssi il existe un mot y de longueur 2q(|x|) tel que M(x, y) = 1.

Propriétés

On a P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME.

D'après le , le classe NP est différente de NEXPTIME (mais incluse)Article original : . Si P = NP alors EXPTIME = NEXPTIMEJuris 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.

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

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.

Jeux Décider si une formule booléenne quantifiée avec dépendance est vraie () est NEXPTIME-complet.. Par conséquent, la version en équipe de joueurs avec information imparfaite de la logique contrainte est NEXPTIME-complète également..

Notes et références

Lien externe

Catégorie:Classe de complexité