Dlaczego twierdzenia Shaefera i Mahaneya nie oznaczają P = NP?

Jestem pewien, że ktoś pomyślał o tym wcześniej lub natychmiast go odrzucił, ale dlaczego teoria dychotomii Schaefera wraz z twierdzeniem Mahaneya o rzadkich zestawach nie implikuje P = NP?

Oto moje rozumowanie: Stwórz język który jest równy SAT, przecięty nieskończonym rozstrzygalnym rzadkim zestawem. Zatem również musi być rzadki. Ponieważ nie jest trywialny, afiniczny, 2-sat lub Horn-sat, według twierdzenia Shaefera musi być NP-zupełny. Ale potem mamy rzadki zestaw NP-zupełny, więc według twierdzenia Mahaneya P = NP. $L$ $L$ $L$

Gdzie się tutaj mylę? Podejrzewam, że źle rozumiem / źle stosuję twierdzenie Shaefera, ale nie rozumiem dlaczego.

— Ari
źródło

Ściśle powiązane: cs.stackexchange.com/q/42544/755 (przeczytaj odpowiedzi, zanim spróbujesz zrozumieć wszystkie szczegóły pytania; odpowiedzi są stosunkowo samodzielne)

— DW

Zastanawiałem się nad tym sam, zanim bardzo dziękuję za pytanie! sztuczka polega na tym, że schaefers thm tak naprawdę nie twierdzi, że nie ma języków pośrednich ”pomiędzy„ P / NP, jest to bardziej subtelne. spróbuj też studiować klasę NPI, znaną też jako średnio zaawansowana NP, istnieje wiele referencji na temat informatyki teoretycznej . wiele głównych problemów to „in” NPI, dwa najważniejsze / znane to faktoring i izomorfizm grafów.

— vzn

w skrócie Shaefer brzmi jak thm o SAT, ale tak naprawdę dotyczy wąskiego języka związanego z SAT, który najwyraźniej nie jest ani NP trudny, ani NP kompletny ...? od dawna szukają prezentacji Shaefer na poziomie „licencjackich podręczników” ....

— dniu

zobacz także wikipedia / NPI / Ladners thm

— vzn

$\mathrm{SAT}(S)$ $\mathrm{CSP}(\Gamma)$ $L$

— Yuval Filmus
źródło

niesamowite, ale czym dokładnie jest SAT (S)? plz wykonujcie to więcej (choć

— prawdę mówiąc

Wyjaśnia to bardzo wyraźnie strona Wikipedii na temat twierdzenia Schaefera, z którego skopiowałem ten zapis.

— Yuval Filmus

ale i tak nadal uważam, że można to wszystko wyjaśnić lepiej. „Schaefer określa problem decyzyjny, który nazywa problemem uogólnionej satysfakcji”. ale najwyraźniej nie jest to tak ogólne ... np. dlaczego język, którego się uczy, jest ważny, a nie wymyślony? czy jest używany gdziekolwiek indziej w CS niż jego praca? jakie są implikacje tego twierdzenia? czy można go w jakiś sposób wykorzystać w ataku P vs NP, czy nie? itp.

— dniu