Problèmes décidables «naturels» connus pour ne pas être en NP.

Chaque fois que j'enseigne la NP-Complétude, les étudiants demandent "y a-t-il des problèmes connus pour ne pas appartenir à NP?"

Comment répondriez-vous? Je leur donne généralement un problème indécidable à titre d'exemple, mais cela ne tourne souvent pas bien: (a) si je leur donne le problème de l'arrêt, ils pensent que c'est un cas d'angle stupide, et (b) si je leur donne des équations diophantiennes, ils Je ne vois pas pourquoi ce n'est pas dans NP (vous pouvez vérifier les solutions en poly-temps ... il suffit de les brancher! J'ai du mal à les désabuser de cette approche.)

J'aimerais leur donner quelque chose comme QBF à titre d'exemple, mais il n'y a pas de séparation prouvée.

Suggestions?

Une possibilité est un problème qui est EXPSPACE-complet. NP est trivialement dans PSPACE, qui est strictement contenu dans EXPSPACE. Un problème qui est EXPSPACE-complet est de décider si une expression régulière qui permet l'exponentiation est tout de $\Sigma^*$ .

Puisque vous mettez l'accent sur les problèmes naturels, voici un problème très naturel -complet qui n'est pas dans N P : Problème de carrelage carré: étant donné un ensemble de carreaux finis, faut-il carreler un carré de taille 2 n x 2 n ?$NEXP$$NP$$2^n$$2^n$

Notez que lorsque la taille du carré est x n ( n est codé en unaire), le problème devient N P -complet.$n$$n$$n$$NP$

Pour la complétude du carrelage carré, vérifiez la référence.$NEXP$

[1] Christos H. Papadimitriou. Complexité informatique. Addison-Wesley, Reading, Massachusetts, 1994

Tout problème complet pour ou 2 E X P T I M E est connu pour ne pas être dans N P (par le théorème de la hiérarchie temporelle). De même pour N E X P S P A C E et E X P S P A C $NEXPTIME$$EXPTIME$$NP$$NEXPSPACE$$EXPSPACE$(par hiérarchie spatiale + simulation). Vous pouvez souvent obtenir de "faux" problèmes en remplissant, mais les problèmes naturels complets pour ces classes ne semblent pas être si courants (probablement parce qu'ils sont incroyablement difficiles!), Mais voici quelques-uns:

EXPSPACE:
équivalence d'expression régulière avec opérateur d'exponentiation

2-EXPTIME:
Satisfaisabilité pour CTL * (une logique temporelle)
Satisfaisabilité pour ATL *
Problème de décision pour l'arithmétique de Presburger

Un exemple simple est la fonction de tétration , qui n'est même pas dans ELEMENTARY . Vous pouvez utiliser une version de décision de cela.

Selon le théorème de la hiérarchie temporelle , si est une fonction constructible dans le temps, et f ( n + 1 ) = o ( g ( n ) ) , alors:$g(n)$$f(n+1) = o(g(n))$

.$\operatorname{NTIME}(f(n)) \subsetneq \operatorname{NTIME}(g(n))$

Ainsi, par exemple, tout problème NEXP-complet n'est pas dans NP. Citation de Wikipedia :

Un ensemble important de problèmes NEXPTIME complets concerne les circuits succincts. Les circuits succincts sont de simples machines utilisées pour décrire des graphiques dans un espace exponentiellement moins. Ils acceptent deux nombres de sommets en entrée et en sortie s'il y a un bord entre eux. Si la résolution d'un problème sur un graphique dans une représentation naturelle, telle qu'une matrice d'adjacence, est NP-complète, la résolution du même problème sur une représentation de circuit succincte est NEXPTIME-complète, car l'entrée est exponentiellement plus petite. À titre d'exemple simple, trouver un chemin hamiltonien pour un graphe ainsi codé est NEXPTIME-complet.

Voir aussi la section "Problèmes succincts" à la page 492 du livre de Papadimitriou .

Un système de canaux est un ensemble d'automates finis avec des canaux de communication sur lesquels ils peuvent envoyer des messages. Un message est une lettre d'un alphabet. Dans un système de canal avec perte, les messages peuvent être abandonnés: une lettre envoyée sur un canal peut disparaître. Le problème d'accessibilité pour les systèmes à canaux avec perte est décidable mais non primitif récursif.

Pour un exemple plus doux, le problème d'accessibilité pour les systèmes d'addition vectorielle est EXPSpace difficile.