Rozważ następujący problem: biorąc pod uwagę formułę CNF i zadanie spełniające tę formułę, czy istnieje inne zadowalające przypisanie dla tej formuły? Jaka jest złożoność tego problemu? (Z pewnością jest w NP, ale czy to jest NP-trudne?) Co się stanie, jeśli nie otrzymasz zadania i chcesz po...
Chcę zrobić pierwszy solver SAT. Znam konkurs SAT i konferencję SAT i jest tak wiele artykułów na ten temat. Jestem starterem, przytłoczonym starterem. Od czego powinienem zacząć W końcu chcę wprowadzić najnowocześniejsze rozwiązania. Chcę porady ekspertów, jak zacząć, żeby nie marnować czasu na...
Co wiadomo o złożoności znalezienia minimalnych obwodów, które obliczają SAT do długości ? nnn Bardziej formalnie: jaka jest złożoność funkcji, która, biorąc pod uwagę jako wejście, generuje minimalny obwód taki, że dla dowolnej formuły z , ?1n1n1^{n}CCCφφ\varphi|φ|≤n|φ|≤n|\varphi| \leq...
Nie do końca rozumiem, dlaczego prawie wszystkie solwery SAT używają CNF zamiast DNF. Wydaje mi się, że rozwiązywanie SAT jest łatwiejsze przy użyciu DNF. W końcu musisz tylko przejrzeć zestaw implantów i sprawdzić, czy jeden z nich nie zawiera zarówno zmiennej, jak i jej negacji. W przypadku CNF...
Niech zmiennymi będą . Odległość między dwiema zmiennymi jest zdefiniowana jako. Odległość między dwoma literałami jest odległością między odpowiednimi dwiema zmiennymi. d ( x a , x b ) = | a - b |x1, x2), x3). . . xnx1,x2,x3...xnx_1 , x_2 , x_3 ... x_nre( xza, xb) = | a - b |d(xa,xb)=|a−b|d(x_a ,...
Kontynuując poprzednie pytanie , jakie są najlepsze obecne dolne granice przestrzeni dla SAT? Przez spację dolną rozumiem tutaj liczbę komórek taśmy roboczej używanych przez maszynę Turinga, która używa binarnego alfabetu taśmy roboczej. Stały składnik addytywny jest nieunikniony, ponieważ TM...
Czy ktoś mógłby wskazać jedną lub więcej stron internetowych, z których można pobrać działającą implementację solvera #SAT? Interesują mnie osoby zwracające dokładną liczbę rozwiązań, a nie
Problem decyzyjny CNF-SAT można opisać następująco: Dane wejściowe: wzór logiczny ϕϕ\phi w spójnej postaci normalnej. Pytanie: Czy istnieje przypisanie zmiennej spełniające ϕϕ\phi ? Rozważam kilka różnych podejść do rozwiązania CNF-SAT za pomocą niedeterministycznej maszyny Turinga z dwiema...
Obecnie jestem zainteresowany pozyskiwaniem (lub konstruowaniem) i badaniem formuł 3-CNF, które są niezadowalające i mają minimalny rozmiar. Oznacza to, że muszą składać się z jak najmniejszej liczby klauzul (najlepiej m = 8) i możliwie jak najmniejszej liczby odrębnych zmiennych (n = 4 lub...
Problem Max-Sat prosi o znalezienie przypisania formuły CNF, która spełnia jak najwięcej klauzul. Dla prostszego problemu SAT istnieje wiele znanych specjalnych przypadków, które można rozwiązać w czasie wielomianowym, np. Możemy rozwiązać 2-SAT w czasie wielomianowym. W przypadku Max-Sat...
Niech będzie zadowalającą formułą CNF z zmiennymi i klauzulami . Niech będzie przestrzenią rozwiązań .F1F1F_1m S F 1 F 1nnnmmmSF1SF1S_{F_1}F1F1F_1 Rozważ problem z określeniem, biorąc pod uwagę , innej formuły CNF z tym samym zestawem zmiennych co , z (ta sama przestrzeń rozwiązania co ), ale z...
Tutaj celem jest zredukowanie arbitralnego problemu SAT do 3-SAT w czasie wielomianowym przy użyciu jak najmniejszej liczby klauzul i zmiennych. Moje pytanie jest motywowane ciekawością. Mniej formalnie chciałbym wiedzieć: „Jaka jest„ najbardziej naturalna ”redukcja z SAT na 3-SAT?” Teraz...
Spełnialności problemem jest to, oczywiście, podstawowym problemem teoretycznym CS. Bawiłem się jedną wersją problemu z nieskończenie wieloma zmiennymi. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Podstawowe ustawienia. Niech będzie niepustym i prawdopodobnie nieskończonym...
Czy podjęto prace nad tym, jak złożoność przypadkowych instancji # 2-SAT zmienia się w zależności od gęstości klauzuli? To znaczy: w jaki sposób trudność liczenia satysfakcjonujących rozwiązań dla losowo generowanej instancji 2-SAT różni się w zależności od gęstości klauzuli? W szczególności, czy...
Czy są jakieś algorytmy rozwiązywania SAT, które nie są oparte na DPLL? Czy wszystkie algorytmy używane przez solwery SAT są oparte na
W przeszłości wdrażałem modele koordynacji, wykorzystując SAT i regularną satysfakcję z ograniczeń jako podstawowy koń roboczy w ich silnikach. Kontynuując tę linię pracy, chciałbym uczynić modele bardziej interaktywnymi, a najlepszym sposobem, jaki to widzę, jest otwarcie solvera więzów, aby nie...
Biorąc pod uwagę , ile k -DNF z n zmiennymi i klauzulami m jest tautologią? (lub ile k- CNN jest niezadowalających?)m,n,km,n,km, n,
Krótka wersja. Oryginalny dowód, że # 2-SAT jest #P- kompletny, pokazuje w rzeczywistości, że te przypadki # 2-SAT, które są zarówno monotoniczne (nie obejmujące negacji żadnych zmiennych), jak i dwustronne (wykres utworzony przez klauzule nad zmienne to wykres dwustronny) są # P-twarde . Zatem...
Jest dobrze wiadomo, że losowy Preparaty -cnf na n zmiennymi c n klauzule unsatisfiable (tj sprzeczności), z dużym prawdopodobieństwem, na wystarczająco dużej stałej C . Tak więc losowe formuły k- CNN (dla c wystarczająco dużych) stanowią naturalny rozkład w niezadowalających formułach boolowskich...
Według klasycznego wyniku Kurody, klasa złożoności NSPACE [ ]nnn (znana również jako NLIN-SPACE) jest właśnie klasą CSL języków kontekstowych . Problem satysfakcji SAT występuje w NSPACE [ ], ponieważ domysły o liniowym rozmiarze dla rozwiązania można sprawdzić z co najwyżej liniowym obciążeniem...