Pytania otagowane jako sat

SAT oznacza boolowski problem satysfakcji.

3
Obliczanie wszelkich informacji o Max-3SAT
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 mieści się w zakresie …
3
Tłumaczenie SAT z HornSAT
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 ogóle”.
2
Dlaczego istnieje ogromna różnica między rozwiązaniami SAT?
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 implementacja walksata wydaje się mieć pewne …
5
Weryfikacja unikalnych rozwiązań SAT
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 prostu zdecydować, czy formuła …
4
Rozpoczęcie pracy z rozwiązaniami SAT
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 rzeczy nieistotne zbyt wcześnie. Wielkie dzięki.
1
Co wiadomo na temat złożoności znalezienia minimalnych obwodów dla SAT?
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 nC(φ)=SAT(φ)C(φ)=SAT(φ)C(\varphi) = SAT(\varphi) (Szczególnie interesują mnie dolne granice). Naiwny deterministyczny algorytm (oblicz …
2
Najlepsza bieżąca dolna granica dla SAT?
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 może wykorzystywać stany wewnętrzne do symulacji dowolnej stałej liczby komórek taśmy …
7
Dlaczego CNF jest używany do SAT, a nie DNF?
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 nie ma …
10
Pobieranie #SAT Solver
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 przybliżenie.
2
Minimalna niezadowalająca formuła 3-CNF
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 więcej), tak że usunięcie co najmniej jednej …
2
Czy istnieje niedeterministyczny algorytm liniowego czasu dla CNF-SAT?
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 taśmami . Uważam, że istnieje NTM, który rozwiązuje CNF-SAT etapami n⋅poly(log(n))n⋅poli(log⁡(n))n \cdot \texttt{poly}(\log(n)) …
2
Rozwiązane w czasie wielomianowe wystąpienia Max-Sat
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 sytuacja jest inna, ponieważ Max-Sat jest trudny dla NP nawet dla formuł …
18 sat  treewidth  max2sat 
3
Najkrótsza równoważna formuła CNF
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 możliwie jak najmniejszą …
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.