Le théorème de Ladner contre le théorème de Schaefer

En lisant l'article "Est-il temps de déclarer la victoire en comptant la complexité?" sur le blog "Godel's Lost Letter and P = NP" , ils ont mentionné la dichotomie pour les CSP. Après quelques liens après, googler et wikipeding, je suis tombé sur le théorème de Ladner :

Théorème de Ladner: Si , alors il y a des problèmes dans qui ne sont pas terminés.${\bf P} \ne {\bf NP}$${\bf NP} \setminus {\bf P}$${\bf NP}$

et au théorème de Schaefer :

Théorème de dichotomie de Schaefer: Pour chaque langage de contrainte sur , si est Schaefer alors est le temps polynomial résoluble. Sinon, est -complete.$\ \Gamma$$\{0, 1\}$$\ \Gamma$${\bf CSP}(\Gamma)$${\bf CSP}(\Gamma)$${\bf NP}$

Je lis ceci pour signifier que, selon Ladner, il y a des problèmes qui ne sont ni ni , mais selon Schaefer, les problèmes sont soit et complétés seulement.${\bf P}$${\bf NP}$${\bf P}$${\bf NP}$

Qu'est-ce que je rate? Pourquoi ces deux résultats ne se contredisent-ils pas?

J'ai pris la version condensée des déclarations du théorème ci-dessus à partir d' ici . Dans sa section "Commentaires finaux", il dit "Ainsi, si un problème est dans mais qu'il n'est pas -complet alors il ne peut pas être formulé comme CSP" .N ${\bf NP} \setminus {\bf P}$${\bf NP}$

Est-ce à dire que les problèmes manquent certaines instances qui sont dans ? Comment est-ce possible?N ${\bf SAT}$${\bf NP}$

Comme l'indique Massimo Lauria, les problèmes de forme CSP ( ) sont assez particuliers. Il n'y a donc pas de contradiction.$\Gamma$

Toute instance de problème de satisfaction de contrainte peut être représentée comme une paire des structures relationnelles et , et on doit décider s'il existe une structure relationnelle homomorphisme de la source à la cible . S T S $(S,T)$$S$$T$$S$$T$

CSP ( ) est un type spécial de problème de satisfaction de contrainte. Il se compose de toutes les paires de structures relationnelles qui sont construites en utilisant uniquement les relations de dans la structure relationnelle cible: CSP ( ) = . Le théorème de Schaefer dit que lorsque ne contient que des relations sur , alors CSP ( ) est soit NP-complet ou en P, mais ne dit rien du tout sur les autres collections d'instances CSP.Γ Γ { ( S , T ) ∣ toutes les relations de  T  viennent de  Γ } Γ { 0 , 1 } $\Gamma$$\Gamma$$\Gamma$$\{(S,T) \mid \text{all relations of } T \text{ are from } \Gamma\}$$\Gamma$$\{0,1\}$$\Gamma$

À titre d'exemple extrême, on peut commencer avec certains CSP ( ) qui sont NP-complets, et des "trous de soufflage" dans le langage. (Ladner l'a fait avec SAT dans la preuve de son théorème.) Le résultat est un sous-ensemble ne contenant que certaines des instances, et plus sous la forme CSP ( ) pour aucun . La répétition de la construction donne une hiérarchie infinie de langages de dureté décroissante, en supposant P ≠ NP.Γ ′ Γ $\Gamma$$\Gamma'$$\Gamma'$

Vous devez comprendre que les problèmes ont une structure que les problèmes S A T génériques n'ont pas. Je vais vous donner un exemple simple. Soit Γ = { { ( 0 , 0 ) , ( 1 , 1 ) } , { ( 0 , 1 ) , ( 1 , 0 ) } $\mathsf{CSP}$$\mathbf{SAT}$$\Gamma=\{\{(0,0),(1,1)\},\{(0,1),(1,0)\}\}$. Cette langue est telle que vous ne pouvez exprimer que l'égalité et l'inégalité entre deux variables. De toute évidence, un tel ensemble de contraintes peut être résolu en temps polynomial.

Je vais vous donner deux arguments pour clarifier la relation entre et les clauses. Notez que tout ce qui suit suppose P ≠ N P .$\mathsf{CSP}$$\mathbf{P}\not=\mathbf{NP}$

Premièrement : les contraintes ont un nombre fixe de variables, tandis que l'encodage des problèmes intermédiaires peut nécessiter de grosses clauses. Ce n'est pas nécessairement un problème lorsque des contraintes aussi importantes peuvent être exprimées comme une conjonction de petites contraintes utilisant des variables auxiliaires. Ce n'est malheureusement pas toujours le cas pour le général .$\Gamma$

Supposons que contienne simplement l' O R de cinq variables. Il est clair que vous pouvez exprimer le O R de moins de variables en répétant les entrées. Vous ne pouvez pas exprimer un O R plus grand parce que la façon de le faire en utilisant des variables d'extension nécessite des disjonctions de littéraux positifs et négatifs. Γ représente les relations sur les variables , pas sur les littéraux . En effet, lorsque vous pensez à 3- S A T comme un C S P, vous avez besoin de Γ pour contenir quatre relations de disjonction avec quelques entrées négatives (de zéro à trois).$\Gamma$$\mathsf{OR}$$\mathsf{OR}$$\mathsf{OR}$$\Gamma$$\mathbf{SAT}$$\mathsf{CSP}$$\Gamma$

Deuxièmement : chaque relation dans peut être exprimée comme un lot de clauses avec (disons) trois littéraux. Chaque contrainte doit être un lot entier de telles clauses. Dans l'exemple des contraintes d' égalité / inégalité vous ne pouvez pas avoir un binaire A N D (relation -à- dire ( 1 , 1 ) ) sans appliquer un binaire niée O R (ie relation ( 0 , 0 ) ) sur les mêmes variables.$\Gamma$$\mathsf{AND}$${(1,1)}$$\mathsf{OR}$${(0,0)}$

J'espère que cela vous montre que les instances obtenues à partir des C S P ont une structure très particulière, qui est imposée par la nature de Γ . Si la structure est trop serrée, vous ne pouvez pas exprimer de problèmes difficiles. $\mathbf{SAT}$$\mathsf{CSP}$$\Gamma$

Un corollaire du théorème de Schaefer est que chaque fois que applique une structure suffisamment lâche pour exprimer des problèmes de décision N P ∖ P , alors le même Γ laisse suffisamment de liberté pour exprimer des instances générales de 3- S A $\Gamma$$\mathbf{NP\backslash P}$$\Gamma$$\mathsf{SAT}$