Problèmes NP-Hard qui ne sont pas en NP mais décidables

31

Je me demande s'il existe un bon exemple pour un problème NP-difficile facile à comprendre qui n'est pas NP-complet et non indécidable?

Par exemple, le problème d'arrêt est NP-Hard, pas NP-Complete, mais il est indécidable.

Je crois que cela signifie que c'est un problème pour lequel une solution peut être vérifiée mais pas en temps polynomial. (Veuillez corriger cette affirmation si ce n'est pas le cas).

soi-même
la source
Un rapide coup d'œil au zoo complexe rend cette question presque idiote - il y a tellement de classes entre NP et R! Bien sûr, nous ne savons pas que toutes les inclusions sont strictes, il y a donc quelque chose d'intéressant ici.
Raphael

Réponses:

33

Par la version non déterministe du théorème de la hiérarchie du temps , nous avons , où \ mathsf {NEXP} est la classe de problèmes pouvant être résolus en temps exponentiel non déterministe. Il suffit donc de considérer tout problème qui est \ mathsf {NP} -hard et dans \ mathsf {NEXP} , mais pas dans \ mathsf {NP} . Par exemple, nous pouvons considérer tout problème \ mathsf {NEXP} -complet , tel queNPNEXPNEXPNPNEXPNPNEXP

  • 3-colorabilité des graphes décrits par des circuits succincts - ou tout autre problème NP-complet sur les graphes - où un "circuit succinct" est un format pour représenter de très gros graphes en entrée: au lieu de la représentation explicite d'un graphe  par exemple par des listes d'adjacence, nous fournissons plutôt un circuit calculant une fonction f:{0,1}n×{0,1}n{0,1} qui calcule les coefficients d'un 2n×2n matrice d'adjacence.

  • (Non-) équivalence de deux expressions régulières, où l'étoile de Kleene est remplacée par la quadrature (répétant un sous-motif exactement deux fois, plutôt que zéro ou plusieurs fois), et où nous demandons si deux de ces expressions régulières représentent des ensembles de chaînes différents.

Notez que dans ce dernier cas, si nous prenons des expressions régulières comme nous en avons l'habitude, y compris l'étoile de Kleene, le problème résultant est -complete: parce que nous avons les confinements , c'est toujours un problème décidable qui est -hard, et non dans .EXPSPACENPNEXPEXPSPACENPNP

Niel de Beaudrap
la source
7

Avertissement: Cette réponse est basée sur l'hypothèse que , une hypothèse que la plupart des scientifiques croient fermement, mais nous devons encore prouver. Cela signifie qu'il est possible que ces problèmes soient dans et donc également -complete.PSPACENPNPNP

Je dirais que les plus simples sont la vraie formule booléenne quantifiée et la géographie généralisée , toutes deux terminées.PSPACE

TQBF reçoit une formule booléenne quantifiée , testez si la formule est vraie, c'est-à-dire que les formules sous la forme est faux, car la définition de sur false donne une fausse déclaration.xyz.[(xy)z]z

La géographie généralisée est un jeu amusant (voir la chaîne de mots ) où vous avez une liste de chaînes (par exemple, les noms de villes) et le joueur 1 commence par dire un nom, et le joueur 2 répond par un nom commençant par la lettre avec laquelle le nom précédent s'est terminé. Ensuite, c'est au tour du joueur 1, jusqu'à ce que quelqu'un se coince (ce jeu est recommandé de jouer comme un jeu à boire où les objets sont des groupes / artistes, des films, des villes, des capitales, des mathématiciens célèbres ou tout ce qui flotte votre bateau. Celui qui ne peut pas répondre dans un délai raisonnable doit bien sûr boire). Le problème formel est énoncé comme la question "le joueur 1 a-t-il une stratégie gagnante" .

Pål GD
la source
9
Je ne pense pas vraiment cette réponse est appropriée, car il y a des classes que nous faisons savoir strictement au- dessus de NP qui peut servir. À tout le moins, vous devriez réviser votre réponse afin qu'au lieu de votre post-script à la fin, vous puissiez dire à la place au début de votre réponse que votre réponse dépend de (un inégalité dont nous sommes convaincus est probablement vraie). --- Ce commentaire est un remplacement d'un commentaire que j'ai supprimé précédemment; désolé pour le spam. NPPSPACE
Niel de Beaudrap