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

27

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

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. Γ{0,1} ΓCSP(Γ)CSP(Γ)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.PNPPNP

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 PNPPNP

Est-ce à dire que les problèmes manquent certaines instances qui sont dans ? Comment est-ce possible?N PSATNP

user834
la source
2
N'y a-t-il pas un léger problème dans la mesure où il faut faire attention à la façon dont on définit «langage de contrainte» et «problème»? Le théorème de Schaefers (pour autant que je m'en souvienne), ne considère que les langues données en prenant la fermeture sous conjonction et la substitution variable de certains ensembles S de relations. Cependant, on peut construire des ensembles de problèmes de contraintes qui ne sont pas couverts par cela, et peuvent donc être traitables mais pas Schaefer. On peut supposer que l'ensemble de problèmes que Ladner construit n'est tout simplement pas définissable en termes de fermeture sous conjonction et de substitution variable d'un ensemble de relations.
MGwynne
1
Je pense que vous devriez changer la dernière phrase car une instance n'a pas de complexité (non triviale), les ensembles d'instances ont de la complexité. Cela signifierait alors qu'aucun ensemble NPI d' instances de n'est exprimable en tant que . C S P ( Γ )SATCSP(Γ)
Kaveh

Réponses:

15

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

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 T(S,T)STST

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 } ΓΓΓΓ{(S,T)all relations of T are from Γ}Γ{0,1}Γ

À 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.Γ Γ ΓΓΓ

András Salamon
la source
23

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 ) } }CSPSATΓ={{(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 PN P .CSPPNP

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

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).ΓORORORΓSATCSPΓ

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.ΓAND(1,1)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. SATCSPΓ

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 T.ΓNPPΓSAT

MassimoLauria
la source
1
Pour ajouter à l'excellente réponse de MassimoLauria; Il n'y a aucune contradiction. Jetez un œil à cet article de Wikipédia qui contient une section qui explique, en termes simples, la relation entre le théorème de Ladner et le théorème de Schaefer.
Mohammad Al-Turkistany
Juste pour être sûr que je comprends, vous dites que la version restreinte de 'S dans le théorème de Schaefer ne peut pas coder une instance arbitraire de 3- S A T ou que des instances de C S P ( Γ ) pourraient croître super-polynomial pour une classe de problèmes 3- S A T ? CSPSATCSP(Γ)SAT
user834
Dans le théorème de Schaefer, plusieurs types de induisent des algorithmes polynomiaux temporels. Je pense (mais je ne suis pas sûr) que certains d'entre eux ne peuvent pas du tout exprimer un 3- S A T générique . Considérez néanmoins Γ comme l'ensemble des "clauses de l'avertisseur sonore 3". Ce sont des polytimes décidables et tout calcul déterministe au temps t peut être codé comme une formule H o r n - S A T de taille p o l y ( t ) . Ainsi, je suppose que vous pouvez coder un calcul exponentiellement long avec un C S P exponentiellement longΓSATΓtHornSATpoly(t)CSP(c.-à-d. exponentiellement de nombreuses variables). Est-ce que ça fait du sens?
MassimoLauria
Je pense que la bonne façon de le dire est que les CSP dans le cadre de Schaefer ne peuvent pas coder un problème NP arbitraire (3-SAT est en fait un problème CSP canonique). Notez qu'il s'agit d'une instruction conditionnelle (sauf si P = NP).
Chandra Chekuri le
@ChandraChekuri, veuillez m'excuser d'être si dense, mais dites-vous que les CSP dans le cadre de Schaefer ne peuvent pas coder des instances arbitraires de 3-SAT? Le CSP peut, en général, coder 3-SAT mais la version restreinte des CSP dans le cadre de Schaefer ne le peut pas?
user834