Problèmes NEXP-complets

Il y a des tonnes de problèmes NP-complets et des sources qui les collectent, par exemple, voir le livre de Garey et Johnson. Je serais également intéressé de voir une liste des problèmes NEXP-complete. Y en a-t-il un disponible? Comme je suppose qu'il n'y en a pas, j'ouvre cette question (est-ce censé être un wiki communautaire? Je ne sais pas ce genre de choses).

Idéalement, la liste devrait couvrir les différents "types" de problèmes NEXP-complete, peut-être avec une redondance saine pour avoir une vue d'ensemble, mais sans trop se répéter. Par exemple, il est bon d'avoir deux ou trois versions succinctes différentes du même problème NP-complet comme exemples, si les codages succincts se présentent sous des formes légèrement différentes. Pas une douzaine. Une façon propre d'ajouter la redondance consiste à ajouter des clauses du formulaire "Aussi NEXP-complet si BLAH". Les clauses du formulaire "Reste NEXP-complet si le graphique d'entrée a un degré au plus BLAH" sont également les bienvenues.

Enfin, permettez-moi d'ajouter une préférence personnelle. Je suis surtout intéressé par les problèmes complets de saveur "algébrique", s'il y en a. Par exemple, mon problème # P-complet préféré est le permanent pour sa saveur algébrique. J'espère que l'égalité NEXP = MIP peut également fournir un joli problème algébrique NEXP-complet que je ne connais pas.

Pour certains problèmes NP-complete, il existe une variante SUCCINCT qui est NEXP-complete.

Un exemple est SUCCINCT HAMILTON PATH:

• Un circuit booléen avec 2 n entrées et une sortie représente un graphe sur 2 ⁿ sommets. Pour déterminer s'il y a un bord entre les sommets i et j , codez i et j en n bits chacun, et alimentez leur concaténation au circuit: il y a un bord entre ces sommets si la sortie du circuit est vraie. Étant donné un tel circuit, y a-t-il un chemin de Hamilton dans le graphique représenté par le circuit?

De même, il y a SUCCINCT 3SAT, SUCCINCT KNAPSACK, etc.

Référence

• Hana Galperin et Avi Wigderson (1983), «Représentations succinctes des graphiques», Information and Control 56: 3, pp. 183–198.

Voir http://arxiv.org/abs/0905.2419 par Gottesman et Irani. Ceci est un bon exemple. Essentiellement, nous sommes tous habitués à l'idée que la satisfaction des contraintes peut être un problème NP-complet (selon la géométrie, etc ...) Cependant, ils considèrent une situation dans laquelle toutes les contraintes sont données à l'avance et la seule chose que vous êtes autorisé varier est la taille du système. Cependant, cela s'avère toujours difficile si vous encodez le problème dans la taille du système. Autrement dit, le problème est spécifié en donnant une chaîne de N bits, donnant la taille du système de 0 à 2 ^ N-1. Ainsi, la taille du système est exponentiellement plus grande que la taille d'entrée. Ils montrent que c'est NEXP-complet (et que l'analogue quantique est QMA_EXP-complet).

Permettez-moi de commencer par le canon:

Étant donné une machine de Turing non déterministe et un entier écrit en binaire, existe-t-il un chemin de calcul de qui accepte la chaîne vide en au plus étapes?$M$$n$$M$$n$

Aussi NEXP-complete si est écrit en unaire et nous demandons au plus étapes.$n$$2^n$

Inégalité des expressions régulières sur (union), (concaténation) et (mise au carré)$\cup$$\cdot$${}^2$ : étant donné deux expressions régulières, représentent-elles des ensembles différents?

Une expression régulière est soit

• $0$ ,
• $1$ ,
• $e\cup f$ ,
• $e\cdot f$ , ou
• $e^2$ .

Ces expressions représentent les ensembles

• $L(0)=\{0\}$ ,
• $L(1)=\{1\}$ ,
• $L(e\cup f)=L(e)\cup L(f)$ ,
• $L(e\cdot f)=\{ab\mid a\in L(e), b\in L(f)\}$ , et
• $L(e^2)=L(e\cdot e)$ ,

respectivement.

Notez que si nous autorisons l'étoile Kleene (zéro ou plusieurs copies d'une expression) comme quatrième opérateur (en plus de l'union, de la concaténation et de la mise au carré), alors le problème de savoir si deux expressions régulières représentent des langues différentes devient EXPSPACE-complet .

LJ Stockmeyer, AR Meyer, " Problèmes de mots nécessitant un temps exponentiel ", 5e STOC, 1973.

SCHÖNFINKEL – BERNAYS SAT

• Une formule en logique du premier ordre appartient à la classe de formules Schönfinkel – Bernays si elle peut être exprimée sous la forme (avec ne contenant aucun quantificateur ou symbole de fonction). Étant donné une formule Schönfinkel – Bernays, a-t-elle un modèle?$∃x_1 ∃x_2 \ldots ∀y_1 ∀y_2 \ldots φ$$φ$

Référence

• HR Lewis (1980), « Complexity results for classes of quantificational formula », Journal of Computer and System Sciences 21, pp. 317–353.