Adhésion non triviale à NP

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 $NP\cap coNP$ ), 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 $NP$qui ne sont pas déterministes.

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

• Christos Papadimitriou, " Sur la complexité de la programmation entière", JACM, 1981.

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$

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$\mathbf{x}.Q(\mathbf{x},\mathbf{y})$$\mathbf{x}$$\mathbf{y}$$Q(\mathbf{x},\mathbf{y})$$\mathbf{x}$$\mathbf{y}$$Q$$I$$\mathbf{t}$ 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ées$\mathbf{x}$$Q(\mathbf{t},\mathbf{y})$$Q_1$$Q_2$$Q_1$$I$$Q_2$$I$$Q_1$$Q_2$ et Q 2 , Q 1 est-il contenu dans Q 2 ?$Q_1$$Q_2$$Q_1$$Q_2$

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.)$Q_1$$Q_1$$Q_2$$Q_2$

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.$Q$$Q$SELECT ... FROM

$Q_1$$Q_2$$Q_1$$Q_2$$Q_2$$Q_1$

• 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

$\Pi^P_2$

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)$$F$$a x_1^2 +b x_1 x_2+ c x_2^2 +d x_1+e x_2 + f = 0$$F$$F$$O(L(F)^5 \log L(F) \log \log L(F))$$\Sigma = \{F : F \text{ 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! :-)

Lorsque la reconnaissance de la reconnaissance du graphique de tolérance était ouverte, l'article suivant a montré qu'elle était en NP:

http://www.sciencedirect.com/science/article/pii/S0166218X04000940

(Plus tard, la reconnaissance du graphique de tolérance s'est révélée être NP complète: http://arxiv.org/abs/1001.3251 )

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:

• Christoph Haase, Stephan Kreutzer, Joël Ouaknine, James Worrell, Reachability in succinct and parametric one-counter automata , CONCUR 2009, LNCS 5710 369–383. doi: 10.1007 / 978-3-642-04081-8_25 ( version étendue )

$NP$$L_1, L_2$$L_1\in NP$$L_2\notin NP$$L$

$L\in NP$$L\in NP$$NP$