W innym wątku Joe Fitzsimons zapytał o „najlepsze obecne dolne granice 3SAT”.
Chciałbym pójść w drugą stronę: jakie są najlepsze obecne górne granice 3SAT? Innymi słowy, jaka jest złożoność czasowa najbardziej wydajnego solvera SAT?
W szczególności, czy można sobie wyobrazić algorytm subwykładniczy (a jednak super-wielomianowy) dla SAT?
cc.complexity-theory
ds.algorithms
sat
upper-bounds
MS Dousti
źródło
źródło
Odpowiedzi:
Istnieją dwa rodzaje „najlepszych” solverów SAT, jeden do teorii, drugi do praktyki.
Teoria
Ćwiczyć
Sprawdź wyniki konferencji SAT dla każdego roku.
źródło
Nie znam żadnej zero błędów randomizowanych algorytmów (lub stożek / Eadvice algorytmów,
dla tej sprawy) dla SAT, które mają lepsze niż granice znanych algorytmów deterministycznych,
niezależnie od tego, czy jest tam obiecał być co najwyżej jeden spełniający zadanie.
twierdzi, że wynik można podsumować następująco:
źródło
Algorytm Schoeninga jest algorytmem probabilistycznym dla k-SAT z czasem działania , gdzie . Powoduje to algorytmu dla 3SAT, algorytmu dla 4SAT itp.O(an) a=2(k−1)/k O(1.33334n) O(1.5n)
Algorytm został również (prawie całkowicie) zdegenerowany przez Mosera i Schedera, którzy podają deterministyczny algorytm rozwiązywania czasu działania kSAT gdzie jest taką samą stałą jak poprzednio, a może być dowolnie małym.O((a+ϵ)n) a ϵ>0
Uwaga: w tej odpowiedzi duża notacja Oh ukrywa czynniki poli (n). Chciałem użyć notacji , ale nie wyświetla się ona poprawnie.O∗
źródło
Jak już wspomniano, jeśli jesteś zainteresowany teoretycznymi gwarancjami czasu pracy, to pytanie jest duplikatem.
Ale chciałbym zauważyć, że jeśli naprawdę chcesz rozwiązać konkretny problem (jak wspomniany problem kolorowania), myślę, że studiowanie teoretycznych górnych granic nie ma żadnego sensu.
Chociaż chciałeś uniknąć aspektów „inżynieryjnych”, sugeruję, abyś wziął kilka popularnych solverów SAT, wypróbował je i zobaczył, co się stanie (większość z nich może odczytać ten sam format pliku DIMACS, więc łatwo jest wypróbować różne solwery). Możesz mieć zarówno pozytywne, jak i negatywne niespodzianki. Ostatnio miałem rodzinę instancji SAT; garść przykładów z dziesiątkami tysięcy zmiennych i ponad milionem klauzul okazała się łatwa do rozwiązania, podczas gdy pozornie znacznie prostsze instancje z zaledwie setkami zmiennych i tysiącami klauzul były zdecydowanie zbyt trudne dla jakiegokolwiek solwera, którego próbowałem.
źródło
źródło
3SAT nie ma algorytmów wykładniczych, chyba że hipoteza wykładniczego czasu jest fałszywa.
źródło
Ten post dotyczy górnych granic SAT. Ten jeden zajmuje najlepszych dolnych granic. Ten link zawiera szczegółowe informacje na temat corocznego konkursu porównującego implementacje solvera SAT, które można pobrać. Dla uproszczenia możesz zacząć od SAT4J , biblioteki opartej na Javie do rozwiązywania problemów SAT.
źródło
Najlepszy algorytm deterministyczny dla 3-SAT ma teraz górną granicę 1.32793 ^ n, patrz https://arxiv.org/abs/1804.07901 autorstwa Sixue Liu. Zasadniczo w tym artykule poprawiono górne granice dla wszystkich k-SAT.
źródło