Dlaczego twierdzenie Schaefera nie dowodzi, że P = NP?

To chyba głupie pytanie, ale po prostu nie rozumiem. W kolejnym pytaniu wymyślili dychotomia twierdzenia Schaefer jest . Dla mnie wygląda na to, że udowadnia, że ​​każdy problem CSP jest w P lub NP-kompletny, ale nie pomiędzy. Skoro każdy problem NP można przekształcić w czasie wielomianowym w CSP (ponieważ CSP jest NP-kompletny), dlaczego nie dowodzi to, że nie ma spacji między P i NP-Complete, a więc P = NP?

Na przykład moje myśli są takie, że faktoryzacja liczb całkowitych może być przepisana jako problem zadowalający, więc używając twierdzenia Schaefera powinno być albo w P albo NP-kompletne, ale nie pomiędzy (nawet jeśli nie możemy dowiedzieć się, który to jest).

Inne spojrzenie na całe pytanie: dlaczego nie możemy użyć twierdzenia Schaefera, aby zdecydować, czy rozkład liczb całkowitych jest w P czy w NP-zupełny?

EDYCJA: w odpowiedzi na odpowiedź Davida Richerby'ego (jest za długa na komentarz):

Ciekawe, ale jeszcze nie do końca rozumiem. Definiując zbiór zależności gamma, stosując twierdzenie Schaefera, możemy nałożyć na niego ograniczenia. Na przykład możemy ograniczyć gamma do używania tylko relacji arity 2 (wtedy problem występuje w P). Jakie ograniczenia możemy nałożyć na gamma?

Dlaczego nie możemy nałożyć takich ograniczeń, że wszystkie wystąpienia CSP (gamma) są dokładnie takie same jak (izomorficzny?) L? Na przykład, podczas przenoszenia faktoryzacji liczb całkowitych na liczby nierównomierne, jeden z dwóch dzielników jest reprezentowany binarnie jako xn .. x3 x2 1. Teraz chcę, aby ta liczba była większa niż 1. Więc mam relację (xn lub .. lub x3 lub x2). Mówię więc, że gamma może mieć relację orną ar-n-1. Ale nie chcę, aby ta relacja lub była wykorzystywana w celu uwzględnienia innych wystąpień niż L w języku, dlatego też narzucam, że x2..xn w relacji or nie jest dozwolone, aby mieć negację. Oczywiście muszę również narzucić ograniczenie, że są tam używane tylko określone zmienne.

Czy w ten sposób nie jest możliwe, aby CSP (gamma) było izomorficzne do faktoryzacji liczb całkowitych? Główne pytanie brzmi: jakie ograniczenia możemy nałożyć na gamma?

EDYCJA 2: w odpowiedzi na odpowiedź Yuvala Filmusa.

Rozumiem twoją odpowiedź i wydaje się poprawna, choć mniej więcej taka sama jak odpowiedź Dawida. Na przykład możemy zredukować faktoryzację do 3-sat, a następnie stwierdzić, że faktoryzacja jest zakończona NP, co jest błędem, ponieważ 3-sat ma inne przypadki, które prawdopodobnie nie są faktoryzowane.

Nie rozumiem tego, kiedy instancja jest (nie) arbitralna. Na przykład 2-SAT również wydaje mi się niearbitralny, ponieważ dozwolone są tylko klauzule arity 2 (chociaż muszę przyznać, że dowód nadal obowiązuje, ponieważ jest to górna granica, aw tym przypadku górna granica to P).

Być może lepszym przykładem jest NP-kompletność: powyższe pytanie. Jeden odpowiadający daje pełny dowód Schaefera. Ale nakładam nietrywialne ograniczenia na dane wejściowe (dozwolone są klauzule 2-SAT i klauzule xor, ale nic więcej). Oczywiście dowód nadal obowiązuje, ponieważ problemy CSP uwzględnione w dowodzie są dokładnie takie same jak oryginalne.

Czego nie rozumiem, dlaczego nie możemy zrobić podobnych dla faktoryzacji? Oczywiście nie ma sensu redukować go do 3-SAT, ale pozwól mi podać instancję CSP, która rozkłada liczbę na czynniki i rozkłada tylko liczbę (4 bity). (przejdź do END-OF-SKIP, jeśli uważasz, że jest to możliwe).

Instancja faktoryzacji.

WEJŚCIE:

$n_4n_3n_2n_1$
$m_4m_3m_2m_1$

Teraz przekształćmy to w instancję CSP

$n_5..n_1$$m_5..m_1$

$d_4d_3d_2d_1$
$e_4e_3e_2e_1$

relacje:

$e_4 \lor e_3 \lor e_2$

$(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)$

$d_1 \land e_1 = n_1$
$(d_1 \land e_2) \oplus (d_2 \land e_1) = n_2$
$n_3 = ... ; n_4 = ...$

KONIEC POMOCY

Sedno polega na tym, że stosując twierdzenie Schaefera, musimy brać pod uwagę tylko takie CSP . (Podobnie jak w przypadku 2-SAT, rozważamy tylko dostawców CSP z arity 2). Czyniąc to, zachowuje się jeden z sześciu polimorfizmów lub nie (nie licząc dziwactw w teorii mnogości). W obu przypadkach faktoryzacja nie jest NP-pośrednia.

Można to również zrobić dla 3-SAT. Następnie powinniśmy rozważyć (używając redukcji) instancje 3-SAT, które reprezentują instancje faktoryzacji (które nie są już 3-SAT).

Gdzie popełniam błąd?

$L$$\Gamma$$\Gamma$$L$$L$$\Gamma$$L$$\Gamma$

$\Gamma$$\mathrm{CSP}(\Gamma)$

$\Gamma$$\mathrm{CSP}(\Gamma)$