Pytania otagowane jako satisfiability

Satysfakcjonalność (SAT) to problem określenia, czy istnieje przypisanie zmiennej, która spełnia daną formułę boolowską.

3
Pomiar trudności wystąpień SAT
Biorąc pod uwagę instancję SAT, chciałbym móc oszacować, jak trudno będzie rozwiązać instancję. Jednym ze sposobów jest uruchamianie istniejących solverów, ale ten rodzaj pokonuje cel oszacowania trudności. Drugi sposób może polegać na szukaniu stosunku klauzul do zmiennych, jak ma to miejsce w przypadku przejść fazowych w losowo-SAT, ale jestem pewien, …
2
Kodowanie ograniczenia 1 na n dla solverów SAT
Używam solwera SAT do zakodowania problemu, a jako część instancji SAT mam zmienne logiczne gdzie jest zamierzone, że dokładnie jedna z nich powinna być prawdziwa, a reszta powinna być fałszywa . (Czasami widziałem to opisywane jako kodowanie „na gorąco”).x1,x2,…,xnx1,x2,…,xnx_1,x_2,\dots,x_n Chcę zakodować ograniczenie „dokładnie jeden z musi być prawdziwe” w SAT. …
2
Czy istnieje czasem skuteczny algorytm do rozwiązania #SAT?
Niech będzie formułą logiczną składającą się ze zwykłych operatorów AND, OR i NOT oraz niektórych zmiennych. Chciałbym policzyć liczbę spełniającą zadania dla . To znaczy, chcę znaleźć liczbę różnych przypisań wartości prawdy do zmiennych dla których przyjmuje wartość prawdziwą. Na przykład formuła ma trzy zadowalające przypisania; ma cztery. To jest …
3
Konwertowanie problemów matematycznych na instancje SAT
Chcę zmienić problem matematyczny, który mam, w logiczny problem satysfakcji (SAT), a następnie rozwiązać go za pomocą SAT Solvera. Zastanawiam się, czy ktoś zna instrukcję, przewodnik lub cokolwiek, co pomoże mi przekonwertować mój problem na instancję SAT. Chcę też rozwiązać ten problem w czasie lepszym niż wykładniczy. Mam nadzieję, że …
1
Klasyfikacja trudnych do rozwiązania / możliwych do rozwiązania wariantów problemu satysfakcji
Ostatnio znalazłem w artykule [1] specjalną symetryczną wersję SAT o nazwie 2/2/4-SAT . Ale istnieje wiele wariantów kompletnych , na przykład: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SAT , ...NPNP\text{NP} Możliwe są inne warianty: - SAT , Planar-NAE- SAT , ...222SATSAT\text{SAT}SATSAT\text{SAT} Czy istnieją artykuły ankietowe (lub strony internetowe), które klasyfikują wszystkie (dziwne) …
1
Obsługa struktur danych dla lokalnego wyszukiwania SAT
WalkSAT i GSAT są dobrze znanymi i prostymi lokalnymi algorytmami wyszukiwania służącymi do rozwiązania logicznego problemu satysfakcji. Pseudokod algorytmu GSAT jest kopiowany z pytania Implementacja algorytmu GSAT - Jak wybrać literał, który ma być odwrócony? i przedstawione poniżej. procedure GSAT(A,Max_Tries,Max_Flips) A: is a CNF formula for i:=1 to Max_Tries do …
1
Implementacja algorytmu GSAT - Jak wybrać literał do przerzucenia?
Algorytm GSAT jest w większości prosty: dostajesz formułę w spójnej normalnej formie i przerzucasz literały klauzul, aż znajdziesz rozwiązanie, które spełnia formułę lub nie osiągniesz limitu max_tries / max_flips i nie znajdziesz rozwiązania. Implementuję następujący algorytm: procedure GSAT(A,Max_Tries,Max_Flips) A: is a CNF formula for i:=1 to Max_Tries do S <- …
3
Dlaczego nie ma algorytmów aproksymacyjnych dla SAT i innych problemów decyzyjnych?
Mam problem z decyzją o zakończeniu NP. Biorąc pod uwagę przykład problemu, chciałbym zaprojektować algorytm, który wyświetli TAK, jeśli problem jest wykonalny, i NIE, w przeciwnym razie. (Oczywiście, jeśli algorytm nie jest optymalny, popełni błędy.) Nie mogę znaleźć algorytmów aproksymacyjnych dla takich problemów. Szukałem w szczególności SAT i na stronie …
3
Książka z przepisami dla kodowań SAT?
Solwery SAT stają się coraz bardziej wydajne w rozwiązywaniu dużych instancji i są używane jako zaplecze w różnych kontekstach. Za każdym razem, gdy chce się ich użyć do rozwiązania problemu w określonej domenie, musi wymyślić kodowanie ad-hoc, które nie tylko ma odpowiedni zestaw rozwiązań, ale także nakłada ograniczenia (nawet nadmiarowe) …
2
Gęsty NP pełny język oznacza P = NP
Mówimy, że język jest gęsty, jeśli istnieje wielomian taki, że dla wszystkichInnymi słowy, dla dowolnej długości istnieje tylko wielomianowo wiele słów o długości , które nie są wJ⊆Σ∗jot⊆Σ∗J \subseteq \Sigma^{*}ppp|Jc∩Σn|≤p(n)|jotdo∩Σn|≤p(n) |J^c \cap \Sigma^n| \leq p(n)n∈N.n∈N..n \in \mathbb{N}.nnnnnnJ.jot.J. Problem, który obecnie badam, wymaga przedstawienia następujących informacji Jeśli istnieje gęsty język , …
2
Jaki jest przykład niezadowalającej formuły 3-CNF?
Próbuję owinąć głowę wokół dowodu kompletności NP, który wydaje się obracać wokół SAT / 3CNF-SAT. Może jest późna godzina, ale obawiam się, że nie mogę wymyślić formuły 3CNF, której nie można spełnić (prawdopodobnie brakuje mi czegoś oczywistego). Czy możesz podać mi przykład takiej formuły?
6
Znalezienie maksymalnego XOR dwóch liczb w przedziale: czy możemy zrobić coś lepszego niż kwadratowy?
Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Naiwny algorytm sprawdza po prostu wszystkie możliwe pary; na przykład w rubinie mielibyśmy: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if …
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.