Adhésion non triviale à NP

27

Y a-t-il un exemple de langue qui est en NP , mais où nous ne pouvons pas prouver ce fait directement en montrant qu'il existe un témoin polynomial d'appartenance à cette langue?

Au lieu de cela, le fait que la langue est en NP serait prouvé en la réduisant à une autre langue en NP , où le lien entre les deux n'est pas trivial et nécessite une analyse approfondie.

Plus généralement, existe-t-il des exemples intéressants de problèmes dans NP sorte qu'il est difficile de voir qu'ils sont dans NP ?

Une demi-réponse serait le problème de décider du vainqueur dans les jeux de parité: pour montrer qu'il est dans NP (même NPcoNP ), nous avons besoin du théorème de la détermination positionnelle qui est profond et non trivial. Cependant, cette réponse n'est pas idéale, car elle se résume toujours à l'existence d'un témoin polynomial pour ce problème exact (la stratégie positionnelle), et ne se réduit pas à un autre problème NP différent.

Un autre serait l'algorithme de primalité AKS: décider si un nombre est premier est polynomial, alors qu'il n'y a a priori pas de petit témoin de ce fait. Disons que nous excluons les "algorithmes polynomiaux surprenants", car beaucoup d'entre eux correspondraient à la description ci-dessus. Je suis plus intéressé par les algorithmes surprenants NPqui ne sont pas déterministes.

Denis
la source
12
Nous savions que les nombres premiers étaient dans NP avant AKS parce que n>2 est premier ssi il y a 1<r<n tel que et pour tous les diviseurs premiers q de , . n - 1 r n - 1rn1=1modnn1rn1q1modn
Artem Kaznatcheev
ah intéressant, je n'ai pas pensé aux certificats de primalité.
Denis
6
Un bon bassin d'exemples d'appartenance non triviale à NP peut provenir de problèmes pour lesquels il est ouvert depuis un certain temps, qu'ils soient même décidables. Deux problèmes du haut de mon chapeau: la reconnaissance des graphes à cordes et la reconnaissance des nœuds (et le genre de nœuds plus général). Dans les deux cas cependant, il existe un témoin polynomial (à savoir des courbes / surfaces normales) - ils ont juste été difficiles à trouver. La nouage est également en NP, et elle est également non triviale: il existe un certificat mais il faut l'hypothèse de Riemann généralisée pour avoir un polynôme lié à sa taille.
Arnaud
Le «problème de l'orbite» n'était pas non plus connu pour être décidable depuis longtemps. Il a finalement été prouvé que c'était P. Le professeur Lipton a un excellent article sur son blog sur l'histoire de ce problème: rjlipton.wordpress.com/2009/09/02/the-orbit-problem
Jagadish
3
Un autre exemple: étant donné un graphique, décidez s'il est parfait. Le problème peut être résolu en temps polynomial, mais il a fallu un certain temps pour prouver qu'il est en NP.
Jagadish

Réponses:

20

Programmation entière .

Montrer que s'il existe une solution entière, alors il existe une solution entière de taille polynomiale est très impliquée. Voir

Kaveh
la source
4
Voir Christos Papadimitriou, Sur la complexité de la programmation entière, JACM 28 765–768. dx.doi.org/10.1145/322276.322287 (cela vaut la peine d'être lu, et seulement quatre pages).
András Salamon
1
Si vous n'avez pas accès à ACM DL, vous pouvez obtenir le document de Papadimitriou ici .
Kaveh
17

Alors que le problème "est le nombre de croisements d'un graphe au plus ?" est trivialement dans NP, l'appartenance NP des problèmes associés pour le nombre de croisement rectiligne et le nombre de croisement de paires ne sont pas très évidents; cf. Bienstock, Quelques problèmes de nombre de croisements probablement difficiles, Calcul discret. Geometry 6 (1991) 443-459, et Schaefer et al., Recognizing graph graphes dans NP, J. Comput. System Sci. 67 (2003) 365-380.k

user13136
la source
13

Mon exemple préféré est un résultat classique de 1977 d' Ashok Chandra et Philip Merlin. Ils ont montré que le problème de confinement des requêtes était décidable pour les requêtes conjonctives. Le problème de confinement des requêtes conjonctives se révèle être équivalent à décider s'il y a un homomorphisme entre les deux requêtes d'entrée. Cela reformule un problème sémantique, impliquant la quantification sur un ensemble infini, en un problème syntaxique, ne nécessitant que la vérification d'un nombre fini d'homomorphismes possibles. Le certificat d'homomorphisme est uniquement de taille linéaire et donc le problème est en NP.


Ce théorème fournit l'un des fondements de la théorie de l'optimisation des requêtes de base de données. L'idée est de transformer une requête en une autre, plus rapide. Cependant, on veut avoir l'assurance que le processus d'optimisation ne crée pas une nouvelle requête qui ne donne pas de réponses sur certaines bases de données où la requête d'origine a produit des résultats.

Formellement, une requête de base de données est une expression de la forme , où est une liste de variables libres, est une liste de variables liées, et est une formule de premier ordre avec les variables et d'une langue avec des symboles de relation. La requête peut contenir des quantificateurs existentiels et universels, la formule peut contenir la conjonction et la disjonction d'atomes relationnels, et la négation peut également apparaître. Une requête est appliquée à une instance de base de données , qui est un ensemble de relations. Le résultat est un ensemble de tuples; quand tuplex y Q ( x , y ) x y Q I t x Q ( t , y ) Q 1 Q 2 Q 1 I Q 2 Ix.Q(x,y)xyQ(x,y)xyQIt dans le résultat est remplacé par alors la formule peut être satisfaite. On peut alors comparer deux requêtes: est contenue dans si chaque fois que appliqué à une instance de base de données arbitraire produit des résultats, puis appliqué à la même instance, produit également des résultats. (C'est OK si Q 1 ne produit pas de résultats mais Q 2 le fait, mais pour le confinement, l'implication doit tenir pour chaque instance possible.) Le problème de confinement des requêtes demande: étant donné deux requêtes de base de donnéesxQ(t,y)Q1Q2Q1IQ2IQ1Q2 et Q 2 , Q 1 est-il contenu dans Q 2 ?Q1Q2Q1Q2

Il n'était pas du tout clair avant Chandra-Merlin que le problème était décidable. En utilisant uniquement la définition, il faut quantifier sur l'ensemble infini de toutes les bases de données possibles. Si les requêtes ne sont pas restreintes, alors le problème est en fait indécidable: soit une formule toujours vraie, alors Q 1 est contenue dans Q 2 si Q 2 est valide. (Il s'agit du problème Entscheidungs de Hilbert , montré indécidable par Church et Turing en 1936.)Q1Q1Q2Q2

Pour éviter l'indécidabilité, une requête conjonctive a une forme plutôt limitée: ne contient que des quantificateurs existentiels, et la négation et la disjonction ne sont pas autorisées. Donc Q est une formule existentielle positive avec seulement une conjonction d'atomes relationnels. Il s'agit d'un petit fragment de logique, mais il suffit d'exprimer une grande proportion de requêtes de base de données utiles. L' instruction classique en SQL exprime des requêtes conjonctives; la plupart des requêtes des moteurs de recherche sont des requêtes conjonctives.QQSELECT ... FROM

Q1Q2Q1Q2Q2Q1

  • Ashok K. Chandra et Philip M. Merlin, Mise en œuvre optimale des requêtes conjonctives dans les bases de données relationnelles , STOC '77 77–90. doi: 10.1145 / 800105.803397

Π2P

András Salamon
la source
4

J'ai trouvé un bon candidat en lisant certains articles sur les équations diophantiennes quadratiques:

JC Lagarias, Certificats succincts pour des solutions aux équations diophantiennes quadratiques binaires (2006)

L(F)Fax12+bx1x2+cx22+dx1+ex2+f=0FFO(L(F)5logL(F)loglogL(F))Σ={F:F has a nonnegative integer solution}

... mais - pour être honnête - la seule preuve que j'ai que ce n'est pas trivial est le nombre de pages du papier ... 62! :-)

Marzio De Biasi
la source
3

Décider de l'accessibilité pour différents types de systèmes à états infinis est parfois décidable, souvent non. Pour certains cas particuliers intéressants, il existe toujours un certificat suffisamment petit et vérifiable, ce qui place ces problèmes dans NP. Voici un traitement soigné pour les automates paramétriques à un compteur:

András Salamon
la source
3

NPL1,L2L1NPL2NPL

L=L1if the twin prime conjecture is true, and L=L2otherwise

LNPLNPNP

Andras Farago
la source
5
L={x:xL2¬m|x|}L2
Joshua Grochow