Jakie są obecnie najlepsze dolne granice 3SAT?
Jakie są najlepsze dolne granice prądu dla czasu i głębokości obwodu dla
46
SAT oznacza boolowski problem satysfakcji.
Jakie są najlepsze dolne granice prądu dla czasu i głębokości obwodu dla
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...
Jakie są teoretyczne wyjaśnienia praktycznego sukcesu solverów SAT i czy ktoś może dać przegląd i wyjaśnienie w stylu „wikipedii” łącząc je wszystkie? Analogicznie, wygładzona analiza ( wersja arXiv )) dla algorytmu simplex świetnie się tłumaczy, dlaczego działa tak dobrze w praktyce, mimo że w...
W tym pytaniu formuła 3CNF oznacza formułę CNF, w której każda klauzula obejmuje dokładnie trzy różne zmienne. Dla stałych 0 < s <1, Gap-3SAT s stanowi następujący problem: GAP 3SAT s wystąpienia : a 3CNF wzór φ. Tak, obietnica : φ jest satysfakcjonująca. No-obietnica : Brak przypisania...
Decydowanie, czy skwantyfikowana formuła boolowska, taka jak ∀ x1∃ x2)∀ x3)⋯ ∃ xnφ ( x1, x2), … , Xn) ,∀x1∃x2∀x3⋯∃xnφ(x1,x2,…,xn),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), zawsze ocenia na prawdę, to klasyczny problem z PSPACE. Można to postrzegać jako...
Czy ktoś odważy się wyjaśnić, jaki jest związek tych kierunków studiów, czy może nawet bardziej konkretną odpowiedź na poziomie problemów? Który obejmuje, który obejmuje niektóre powszechnie akceptowane formulacje. Jeśli dobrze to zrozumiałem, przechodząc z SAT do SMT, po prostu wchodzisz w pole...
Zdefiniuj ioioio - jako klasę języków taką, że istnieje język i dla nieskończenie wielu , i zgadzają się we wszystkich przypadkach długości n . (To jest klasa języków, które można „rozwiązywać nieskończenie często, w podwykonawczym czasie”).SUBEXPSUBEXPSUBEXPL ′ ∈ ∩ ε >...
Słyszałem, że w fizyce statystycznej istnieją heurystyczne argumenty, które dają wyniki w teorii prawdopodobieństwa, dla których rygorystyczne dowody są albo nieznane, albo bardzo trudne do uzyskania. Jaki jest prosty zabawkowy przykład takiego zjawiska? Byłoby dobrze, gdyby odpowiedź obejmowała...
Klasyczne algorytmy mogą rozwiązać 3-SAT w czasie (losowo) lub (deterministycznie). (Odnośnik: najlepsze górne granice na SAT )1,3303 n1,3071n1.3071n1.3071^n1,3303n1.3303n1.3303^n Dla porównania, użycie algorytmu Grovera na komputerze kwantowym i zapewniło rozwiązanie w losowaniu losowym . (Może...
Rozważ problem 3-SAT na n zmiennych. Liczba możliwych odrębnych klauzul wynosi: C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text. Liczba przypadków problemem jest ilość wszystkich podzbiorów zestawu...
Wpis na blogu Scotta Aaronsona przedstawił dziś listę interesujących otwartych problemów / zadań w złożoności. Jeden zwrócił moją uwagę: Zbuduj bibliotekę publiczną instancji 3SAT z jak najmniejszą liczbą zmiennych i klauzul, które mogłyby mieć godne uwagi konsekwencje, jeśli zostaną rozwiązane....
W solverach SAT często można znaleźć metody płaszczyzny cięcia, zmienną propagację, odgałęzienie i wiązanie, uczenie się klauzul, inteligentne cofanie, a nawet ręcznie tkaną ludzką heurystykę. Jednak przez dziesięciolecia najlepsze solwery SAT polegały w dużej mierze na technikach sprawdzania...
Jakie są „łatwe regiony” dla satysfakcji? Innymi słowy, wystarczające warunki, aby niektóre solver SAT mógł znaleźć zadowalające zadanie, pod warunkiem, że istnieje. Jednym z przykładów jest sytuacja, w której każda klauzula dzieli zmienne z kilkoma innymi klauzulami, ze względu na konstruktywny...
Czytając artykuł „Czy nadszedł czas, aby zadeklarować zwycięstwo w liczeniu złożoności?” na blogu „Godel's Lost Letter and P = NP” wspominali o dychotomii CSP. Po kilku linkach, googlowaniu i wikipedii natknąłem się na twierdzenie Ladnera : Twierdzenie Ladnera: jeśli , wówczas występują problemy...
Czy można przetłumaczyć wzór B logiczny na równoważną kombinację klauzul Horna? Artykuł w Wikipedii na temat HornSAT wydaje się sugerować, że tak, ale nie byłem w stanie ścigać żadnego odniesienia. Zauważ, że nie mam na myśli „w czasie wielomianowym”, ale raczej „w...
Niektóre problemy trudne NP, które są wykładnicze na grafach ogólnych, są sub wykładnicze na grafach płaskich, ponieważ szerokość wynosi co najwyżej i są wykładnicze w szerokości.4,9 | V.( G ) |------√4.9|V(G)|4.9 \sqrt{|V(G)|} Zasadniczo jestem zainteresowany, czy istnieją algorytmy...
Interesuje mnie krytyczna gęstość 3-satysfakcji (3-SAT) . Przypuszcza się, że takie α istnieje: jeśli liczba losowo wygenerowanych klauzul 3-SAT wynosi ( α + ϵ ) n lub więcej, są prawie na pewno niezadowalające. (Tutaj ϵ jest dowolną małą stałą, a n jest liczbą zmiennych.) Jeśli liczba wynosi ( α -...
O wzorze 3CNF pozwolić jest w maksymalna liczba zadowoleni klauzul jakimkolwiek wyznaczeniem . Wiadomo, że wartość Max-3SAT jest trudna do przybliżenia (z zastrzeżeniem P ≠ NP), tj. Nie ma algorytmu czasu policyjnego, którego dane wejściowe to formuła 3CNF , a których wynikiem jest liczba taka, że...
Dobrze znaną cechą instancji SAT jest stosunek liczby klauzul do liczby zmiennych , tj. Iloraz . Dla każdego istnieje wartość progowa st \ dla , większość instancji jest zadowalająca, a dla większość instancji jest niezadowalająca. Przeprowadzono wiele badań dotyczących problemów, w których , oraz...
Rozwiązują SAT są bardzo ważne w algebraicznych ataków , na przykład walksat i minisat . Jednak przy rozwiązywaniu problemów z testami porównawczymi dostępnymi tutaj istnieje ogromna różnica w wydajności między nimi - Walksat jest znacznie szybszy niż minisat dla tych problemów. Dlaczego to? Ta...