Problèmes 2-NEXPTIME-complete

Nous avons un problème et nous avons trouvé un algorithme qui semble être 2-nexptime.

Je voudrais trouver des problèmes connus de 2-nexptime-complete afin de trouver une borne inférieure.

J'ai trouvé dans la littérature principalement deux de ces problèmes:

si PCP comme solution de taille inférieure à $2^{2^n}$
et le problème du labour pour un carré de taille $2^{2^n}$

Cependant je n'ai pas pu encoder ces problèmes dans le mien. Je voudrais donc connaître d'autres problèmes complets de 2-NEXPTIME, d'abord pour avoir plus d'intuition sur cette classe, et ensuite dans le meilleur des cas prouver une borne inférieure.

Je ne donne pas ici le problème exprès afin d'avoir un large aperçu de 2-NEXPTIME.

Merci

complexity-classes time-complexity complexity wece
la source

Confinement des programmes récursifs de Datalog dans les unions de requêtes conjonctives (Chaudhuri / Vardi 1997). Il devrait également y avoir d'autres problèmes de logique ou de base de données complétés par 2NEXP, mais aucun autre problème spécifique ne vient à l'esprit.

András Salamon

@ AndrásSalamon Merci pour votre réponse. Je n'ai pas trouvé la référence que vous avez indiquée. Tout ce que j'ai trouvé est un article antérieur des auteurs qui déclare que ce problème est 2-EXP-complet (et non 2-NEXP). Suis-je en train de manquer quelque chose.?

wece

vous avez raison, j'ai mal mémorisé le résultat: le problème est 2EXP complet.

András Salamon

J'écrirais toujours ceci comme N2ExpTime plutôt que 2NExpTime, car "2" et "Exp" se réfèrent tous deux à la valeur de la limite de temps supérieure, tandis que "N" se réfère au modèle de machine. Il ne semble pas naturel de placer le modèle de la machine au milieu.

mak

Quelqu'un peut-il me donner la référence pour l'exhaustivité 2-NEXPTIME du PCP avec une solution de longueur inférieure à 2 ^ 2 ^ n s'il vous plaît?

Corto

Réponses:

Le problème évident de N2Exp est bien sûr le problème d'acceptation des mots pour les machines de Turing non déterministes à limite de temps 2exp. Son utilisation peut être aussi difficile / facile que la mosaïque 2exp, car la simulation d'un tel calcul de machine de Turing nécessite essentiellement de définir une grille double exponentielle (2exp de nombreuses configurations de bandes de mémoire de longueur 2exp chacune) qui est ensuite remplie d'une manière non déterministe. En pratique, montrer N2Exp se limite souvent à construire une telle grille (et à s'assurer qu'il ne s'agit pas d'un arbre ou de quelque chose d'autre de structure insuffisante). Le "N" (non-déterminisme) est souvent une partie inhérente du problème et pas si difficile à obtenir une fois que vous avez une grille suffisamment grande (sinon, on pourrait peut-être tirer pour 2exp au début).

Un autre problème pratique avec N2ExpTime est le raisonnement dans les logiques de description expressives (DL). En particulier, le DL $\mathcal{SROIQ}$ $\mathcal{SROIQ}$ $\mathcal{SROIQ}$ pourrait être inspirant de voir comment créer de si grandes grilles.

Le pavage montre également un autre schéma général: N2Exp est vraiment comme NP, il vous suffit de trouver un moyen d'encoder des instances de problème encore plus importantes de manière très efficace. En principe, vous pouvez essayer d'étendre tout problème de NP. La raison pour laquelle le carrelage est agréable est que vous avez seulement besoin de mettre à l'échelle la taille de la grille dans ce cas (qui est plutôt uniforme).

D'un autre côté, si votre problème n'est peut-être que 2ExpTime-complet, vous pouvez vous en sortir avec une simulation de machine de Turing alternativement limitée dans l'espace . Si vous rencontrez des problèmes pour créer une grille 2exp, mais que vous pouvez atteindre des tailles exponentielles, cela peut valoir la peine d'être essayé.

mak
la source