Pytania otagowane jako sat

SAT oznacza boolowski problem satysfakcji.

1
Konsekwencje
Mam część próbnej próby ⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}. Próba dowodowa polega na zmniejszeniu karpu z⊕P⊕P\oplus \mathbf{P}-kompletny problem ⊕⊕\oplus3-REGULARNA POKRYWA VERTEX do SAT. Biorąc pod uwagę sześcienny wykres GGG, redukcja generuje wzór CNF FFF posiadający obie następujące właściwości: FFF ma co najwyżej 111 spełniające zadanie. FFF jest zadowalający tylko i tylko …
2
Ograniczona liczba zmiennych wystąpień w SAT 1-w-3
Czy jest znany wynik dotyczący klasy złożoności 1-w-3-SAT z ograniczoną liczbą zmiennych zdarzeń? Wymyśliłem następującą oszczędną redukcję u Petera Nightingale'a, ale chcę zacytować coś, jeśli jest to znane. Oto sztuczka, którą wymyśliliśmy. To pokazuje, że 1-w-3-SAT ograniczony do 3 wystąpień na zmienną jest NP kompletny i #P zakończony (ponieważ 1-w-3-SAT …
1
Model obliczeniowy w SETH
Impagliazzo, Paturi i Calabro, Impagliazzo, Paturi wprowadzili hipotezę czasu wykładniczego (ETH) i hipotezę silnie wykładniczego czasu (SETH). Z grubsza, SETH mówi, że nie ma algorytmu, który rozwiązuje SAT w czasie . 1,99n1,99n1.99^n Zastanawiałem się, co to znaczy złamać SETH. Zdecydowanie musimy znaleźć algorytm, który rozwiązuje SAT w mniej niż krokach, …
2
Jaka jest korelacja między wysokością a twardością instancji dla losowego 3-SAT?
Ten ostatni artykuł z FOCS2013, Strong Backdoors to Bounded Treewidth SAT autorstwa Gaspersa i Szeidera mówi o związku między szerokością wykresu klauzuli SAT a twardością instancji. W przypadku losowych instancji 3-SAT, tj. Instancji losowo wybranych 3-SAT, jaka jest korelacja między szerokością wykresu klauzulowego a twardością instancji? „Twardość wystąpienia” może być …
2
Wymień wszystkie rozwiązania problemu SAT
Wszystkie znane mi solwery #SAT, np. RelSat, C2D, zwracają tylko liczbę zadowalających wystąpień. Ale chcę poznać każdy z tych przypadków? Czy istnieje taki solver #SAT lub jak powinienem zmodyfikować dostępny solver #SAT, aby to zrobić? Dziękuję Ci.
11 lo.logic  sat  software 
1
Zwiększanie konkurencyjności solverów SAT dzięki wyspecjalizowanym algorytmom
Jakie są przeszkody w konkurowaniu solverów SAT ze specjalistycznymi algorytmami graficznymi? Innymi słowy, czy jest możliwe oczekiwanie od solverów SAT, które mogą zastąpić rolę projektanta algorytmów - tj. Być w stanie automatycznie rozpoznać strukturę problemu, a następnie rozwiązać go tak szybko, jak specjalistyczny algorytm? Oto kilka przykładów, które moim zdaniem …
3
Gdzie mogę uzyskać pomoc w zakresie badań / publikacji?
Od jakiegoś czasu opracowuję algorytm SAT i doszedłem do punktu, w którym chciałbym się nim podzielić. Nie znam wielu ludzi informatyki i nie jestem pewien, dokąd się zwrócić. Zastanawiam się, jakie zasoby są dostępne dla kogoś z algorytmem, który rozważa publikację. Potrzebuję również pomocy w analizie czasu działania i poprawności …
2
Minimalny True Monotone 3SAT
Interesuje mnie odmiana SAT, w której wzór CNF jest monotoniczny (żadnych zmiennych nie neguje się). Taka formuła jest oczywiście zadowalająca. Ale powiedzmy, że liczba prawdziwych zmiennych jest miarą tego, jak dobre jest nasze rozwiązanie. Mamy więc następujący problem: MINIMALNY PRAWDZIWY MONOTON 3SAT INSTANCJA: Zestaw U zmiennych, zbiór C rozłącznych klauzul …
1
Czy SAT w ograniczonej szerokości jest rozstrzygalny w przestrzeni logów?
Elberfeld, Jakoby i Tantau 2010 ( ECCC TR10-062 ) dowiodły, że zajmująca mało miejsca wersja twierdzenia Bodlaendera. Wykazali, że w przypadku wykresów o szerokości co najwyżej rozkład drzewa o szerokości k można znaleźć za pomocą przestrzeni logarytmicznej. Stały współczynnik w ograniczonej przestrzeni zależy od k . (Twierdzenie Bodlaendera pokazuje liniowe …
1
Poprawiasz ogólną redukcję Cooka dla Clique do SAT?
Jestem zainteresowany zredukowaniem kliki do SAT bez powiększania instancji.kkk Klika jest w NP, więc można ją zredukować do SAT za pomocą przestrzeni logarytmicznej. Prosta redukcja podręcznika Garey / Johnson wysadza instancję do sześciennej wielkości. Jednak Klika jest w P dla każdego ustalonego k, więc „powinna” być skuteczna redukcja przynajmniej dla …
4
Prosty przypadek SAT, który nie jest łatwy do rozpoznania drzewa
Czy istnieje naturalna klasa formuł CNF - najlepiej taka, która była wcześniej badana w literaturze - o następujących właściwościach:doCC jest łatwym przypadkiem SAT, takim jak np. Horn lub 2-CNF, tj. Członkostwo w C można badać w czasie wielomianowym, a wzory F ∈ C można badać pod kątem satysfakcji w czasie …
2
O Inverse 3-SAT
Kontekst : Kavvadias i Sideri wykazali, że odwrotny problem 3-SAT jest coNP zakończony: Biorąc pod uwagę ϕϕ\phi zestaw modeli nnn zmiennych, czy istnieje wzór 3-CNF taki, że ϕϕ\phi jest jego dokładnym zestawem modeli? Powstaje formuła bezpośredniego kandydata, która jest połączeniem wszystkich 3-klauzul spełnionych przez wszystkie modele w ϕϕ\phi . Ponieważ …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.