Pourquoi le théorème de Schaefer ne prouve-t-il pas que P = NP?

C'est probablement une question stupide, mais je ne comprends tout simplement pas. Dans une autre question, ils ont proposé le théorème de dichotomie de Schaefer . Pour moi, il semble que cela prouve que chaque problème CSP est soit en P soit en NP-complet, mais pas entre les deux. Étant donné que chaque problème NP peut être transformé en temps polynomial en CSP (car CSP est NP-complet), pourquoi cela ne prouve-t-il pas qu'il n'y a pas d'espace entre P et NP-Complete et que P = NP?

Par exemple, mes pensées vont comme si la factorisation entière peut être réécrite comme un problème de satisfiabilité, donc en utilisant le théorème de Schaefer, il devrait être soit en P soit en NP-complet mais pas entre les deux (même si nous ne pouvons pas trouver lequel c'est).

Une manière différente de voir la question dans son ensemble: pourquoi ne pouvons-nous pas utiliser le théorème de Schaefer pour décider si la factorisation entière est en P ou en NP-complet?

EDIT: en réponse à la réponse de David Richerby (c'est trop long pour un commentaire):

Intéressant, mais je ne comprends pas encore complètement. Lors de la définition de l'ensemble des relations gamma en utilisant le théorème de Schaefer, nous pouvons lui imposer des restrictions. Par exemple, nous pouvons restreindre le gamma à utiliser uniquement des relations d'arité 2 (alors le problème est en P). Quel genre de restrictions pouvons-nous imposer au gamma?

Pourquoi ne pouvons-nous pas imposer de telles restrictions que toutes les instances de CSP (gamma) sont exactement les mêmes que (isomorphes à?) L? Par exemple, lors de la transposition de la factorisation entière pour des nombres inégaux, l'un des deux diviseurs est binaire représenté par xn .. x3 x2 1. Maintenant, je veux que ce nombre soit supérieur à 1. Donc, j'ai la relation (xn ou .. ou x3 ou x2). Je dis donc que le gamma peut avoir une ou-relation d'arité n-1. Mais je ne veux pas que cette relation or soit utilisée pour inclure d'autres instances que L dans le langage, donc j'impose en outre que x2..xn dans la relation or ne soit pas autorisé à avoir une négation. Bien sûr, je dois également imposer la restriction selon laquelle seules des variables spécifiques y sont utilisées.

N'est-il pas possible de cette façon de laisser le CSP (gamma) isomorphe à la factorisation entière? La question principale est: quel genre de restrictions pouvons-nous imposer au gamma?

EDIT 2: en réponse à la réponse de Yuval Filmus.

Je comprends votre réponse et elle semble correcte, bien qu'elle soit à peu près la même que la réponse de David. Par exemple, nous pouvons réduire la factorisation à 3 sat, puis conclure que la factorisation est NP terminée, ce qui est faux car 3 sat a d'autres instances qui ne sont probablement pas de factorisation.

La partie que je ne comprends pas, c'est quand une instance est (non) arbitraire. Par exemple, 2-SAT me semble également non arbitraire, car seules les clauses d'arité 2 sont autorisées (bien que je dois admettre que la preuve est toujours valable car il s'agit d'une limite supérieure et dans ce cas, la limite supérieure est P).

Un meilleur exemple est peut-être un NP-exhaustivité: la question liée ci-dessus. Un répondeur donne une preuve complète de Schaefer. Mais j'impose des restrictions non triviales à l'entrée (les clauses 2-SAT sont autorisées et les clauses xor, mais rien d'autre). Bien sûr, la preuve tient toujours parce que les problèmes CSP considérés dans la preuve sont exactement les mêmes que ceux d'origine.

La partie que je ne comprends pas, c'est pourquoi nous ne pouvons pas faire de même pour la factorisation? Bien sûr, il ne sert à rien de le réduire à 3-SAT, mais permettez-moi de donner l'instance CSP qui factorise un nombre et ne factorise qu'un nombre (de 4 bits). (passez à FIN DE SAUT si vous pensez que cela est possible).

Instance de factorisation.

CONTRIBUTION:

(N =) (les 4 bits du nombre à factoriser) (M =) (les 4 bits de la valeur minimale du premier diviseur) $n_4n_3n_2n_1$
$m_4m_3m_2m_1$

Maintenant, transformons cela en une instance CSP

ENTRÉE:
domaines unaires pour et pour (représentant que N et M sont donnés)$n_5..n_1$$m_5..m_1$

variables avec domaine {0,1}:
(D =) (le premier diviseur) (E =) (le deuxième diviseur)$d_4d_3d_2d_1$
$e_4e_3e_2e_1$

rapports:

$e_4 \lor e_3 \lor e_2$ (représentant E> 1)

$(d_4 \land \neg m_4) \lor (d_4=m_4 \land d_3 \land \neg m_3) \lor (d_4=m_4 \land d_3=m_3 \land d_2 \land \neg m_2) \lor (d_4=m_4 \land d_3=m_3 \land d_2=m_2 \land d_1 \land \neg m_1)$
(représentant D> M)

( d 1 ∧ e 2 ) ⊕ ( d 2 ∧ e 1 ) = n 2 n 3$d_1 \land e_1 = n_1$ (représentant la multiplication de bits la moins significative) (représentant la prochaine multiplication de bits)
$(d_1 \land e_2) \oplus (d_2 \land e_1) = n_2$
$n_3 = ... ; n_4 = ...$

FIN DE SAUT

Le nœud est que, lors de l'application du théorème de Schaefer, nous ne devons considérer que ces CSP . (Tout comme pour le 2-SAT, nous ne considérons que les CSP avec l'arité 2). En faisant cela, l'un des six polymorphismes tient, ou il ne le fait pas (sauf quelques bizarreries dans la théorie des ensembles). Dans les deux cas, la factorisation n'est pas intermédiaire NP.

Cela peut également être fait pour 3-SAT. Ensuite, nous ne devrions considérer (en utilisant la réduction) que les instances 3-SAT qui représentent des instances de factorisation (qui ne sont plus 3-SAT).

Où est-ce que je me trompe?

Lorsque vous traduisez un problème  NP arbitraire en CSP, vous vous retrouvez avec un ensemble d'instances avec un langage de contrainte (ensemble de relations)  . Ce que le théorème de Schaeffer dit, c'est que décider de toutes les instances de CSP ( ) est soit en P, soit NP- complet. Mais, si vous avez seulement besoin de décider d'un ensemble restreint d'instances (par exemple, les instances que vous obtenez en traduisant le problème  ), cela pourrait être plus facile. En particulier, si  est NP- intermédiaire, alors la résolution des instances correspondantes de CSP ( ) serait également NPΓ Γ L L Γ L $L$$\Gamma$$\Gamma$$L$$L$$\Gamma$-intermédiaire - vous pouvez simplement traduire les instances en instances de  et les résoudre là-bas. Mais résoudre la classe de toutes les instances CSP ( ) serait NP- complet.$L$$\Gamma$

Le théorème de Schaefer couvre une situation très spécifique: on vous donne un ensemble fini de relations, et vous vous intéressez à la complexité de . Le théorème de Schaefer vous donne un algorithme pour décider si ce problème est NP-complet ou en P. Il ne couvre aucune autre situation.C S P ( Γ $\Gamma$$\mathrm{CSP}(\Gamma)$

Lorsque vous traduisez un problème comme la factorisation entière en CSP, vous utiliserez un ensemble de relations telles que est NP-complet (ceci, étant donné la croyance commune que la factorisation entière n'est pas dans P ). Mais vos instances ne sont pas arbitraires, donc le théorème de Schaefer ne donne qu'une limite supérieure sur la complexité. Il se pourrait bien que la factorisation entière ne soit en fait pas NP-complète.C S P ( Γ $\Gamma$$\mathrm{CSP}(\Gamma)$