Problèmes NEXP-complets

31

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.

slimton
la source
2
Wiki de la communauté!
Dave Clarke
Comment le transformer en wiki communautaire?
slimton
Signalez le message à l'attention du modérateur et demandez-lui de le faire CW.
Kaveh
5
pourquoi NEXP? c'est-à-dire pourquoi pas une autre classe?
Suresh Venkat
1
Notez que la classe NEXP est parfois également appelée NEXPTIME. Cela pourrait révéler des résultats supplémentaires lors de l'utilisation des moteurs de recherche.
Hermann Gruber

Réponses:

26

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 n 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.
Gareth Rees
la source
17

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

hastings mats
la source
15

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?MnMn

Aussi NEXP-complete si est écrit en unaire et nous demandons au plus étapes.n2n

slimton
la source
15

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

Une expression régulière est soit

  • 0 ,
  • 1 ,
  • ef ,
  • ef , ou
  • e2 .

Ces expressions représentent les ensembles

  • L(0)={0} ,
  • L(1)={1} ,
  • L(ef)=L(e)L(f) ,
  • L(ef)={abaL(e),bL(f)} , et
  • L(e2)=L(ee) ,

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.

Sadeq Dousti
la source
14

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?x1x2y1y2φφ

Référence

Gareth Rees
la source
L'inverse (insatisfaction) est-il coNEXP-complet?
gigaoctets
J'ai toujours pensé qu'une formule logique de premier ordre φ sans quantificateurs est une formule booléenne. N'est-ce pas? Mais pour une formule booléenne φ ce serait Σ ^ P_2 complet. Les variables d'une formule de Schönfinkel-Bernay peuvent-elles avoir d'autres valeurs que true et false?
BeniBela
@BeniBela: Ce sont des formules de logique de premier ordre, donc peut contenir des symboles de relation (dont la signification doit être spécifiée par le modèle). Voir la référence. Si le modèle est limité à deux éléments, nous avons BINARY SCHÖNFINKEL – BERNAYS SAT, qui reste NEXP-complete . φ
Gareth Rees