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 L również musi być rzadki. Ponieważ L 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.
Gdzie się tutaj mylę? Podejrzewam, że źle rozumiem / źle stosuję twierdzenie Shaefera, ale nie rozumiem dlaczego.
Odpowiedzi:
źródło