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

13

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?

Fixee
la source
1
cela devrait-il être CW? c'est une grande liste ...
Suresh Venkat
@Suresh, Cela dépend de votre notion de naturel. Elle devrait être courte si nous nous limitons à un niveau "assez naturel" pour les étudiants.
Mohammad Al-Turkistany
2
Le jeu de Go est terminé sur PSPACE. Le jeu de la vie de Conway est indécidable (c'est-à-dire qu'il est équivalent à Turing Machine) ... sont-ce le type d'exemples que vous vouliez?
user834
1
Décider si un coup est optimal dans un échiquier est E X P T I M E - c o m p l e t e . nXnEXPTIMEcomplete
chazisop
2
@chazisop on ne sait pas si contient bien N P . EXPTIMENP
Mark Reitblatt

Réponses:

13

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

Suresh Venkat
la source
Que signifie votre notation ? L(R)=L(RRR)
Neel Krishnaswami
Il généralise la quadrature (en prenant exactement deux copies). Notez que la fermeture de Kleene prend arbitrairement de nombreuses copies
Suresh Venkat
1
C'est donc la même chose que ? Ou des répétitions infinies sont-elles incluses? L(R)=nNL(Rn)
Neel Krishnaswami
Je ne pense pas que des répétitions infinies soient incluses.
Suresh Venkat
Merci et désolé pour l'horrible pédanterie. L'utilisation de est généralement claire dans son contexte, mais je n'en avais pas. :)
Neel Krishnaswami
11

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

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

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

Mohammad Al-Turkistany
la source
Fascinant. Le pavage d'un carré de taille , où n est représenté en unaire, est NP-complet; et le pavage d'un carré de 2 n × 2 n , où n est représenté en binaire, est NEXP-complet. C'est ça l'idée? Connaît-on la complexité de la mosaïque d'un carré n × nn est représenté en binaire? Ou vouliez-vous dire que n est représenté en unaire même pour la première phrase de votre réponse? n×nn2n×2nnn×nnn
DW
Oui pour votre dernière question.
Mohammad Al-Turkistany
Le pavage carré est NEXP-complet lorsque n est représenté en binaire. n×nn
Mohammad Al-Turkistany
10

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 ENEXPTIMEEXPTIMENPNEXPSPACEEXPSPACE(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

Mark Reitblatt
la source
3
L'arithmétique de Skolem, qui est une arithmétique avec multiplication mais pas addition, est également décidable. Le fait que vous puissiez décider de la théorie du premier ordre de l'un mais pas à la fois de l'addition et de la multiplication me semble un fait assez important.
Neel Krishnaswami
5

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.

Aaron Sterling
la source
4

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

.NTIME(f(n))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 .

MS Dousti
la source
2

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.

Vijay D
la source