Pytania oznaczone «satisfiability»

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...

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ę...

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...

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...

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...

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...

Jak mogę udowodnić, że konwersja z CNF do DNF jest NP-trudna? Nie proszę o odpowiedź, tylko kilka sugestii na temat tego, jak to

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...

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...

Po wydaniu biblioteki AIGER do obsługi wykresów i inwerterów w pewnym momencie w 2006 r. (Tak mi się wydaje), niektóre solvery z obwodami SAT zostały wydane w latach 2006-2008, a na kilku wyścigach / konkursach SAT były ścieżki AIG. Jednak od tego czasu wydaje się, że skupiono się całkowicie na SMT...

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...

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...

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...

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|...

Tak więc, jak wiadomo, problem decyzyjny ILP 0-1 jest NP-zupełny. Pokazanie tego w NP jest łatwe, a pierwotna redukcja pochodziła z SAT; od tego czasu wykazano, że wiele innych problemów z NP-Complete ma formulacje ILP (które działają jako redukcje tych problemów do ILP), ponieważ ILP jest bardzo...

Planar 3SAT jest kompletny z NP. Płaska instancja 3SAT jest instancją 3SAT, dla której wykres zbudowany przy użyciu następujących reguł jest płaski: dodaj wierzchołek dla każdegoxixix_i i xi¯xi¯\bar{x_i} dodać wierzchołek dla każdej klauzuli CjCjC_j dodaj krawędź dla każdej pary...

Jestem pewien, że ktoś pomyślał o tym wcześniej lub natychmiast go odrzucił, ale dlaczego teoria dychotomii Schaefera wraz z twierdzeniem Mahaneya o rzadkich zestawach nie implikuje P = NP? Oto moje rozumowanie: Stwórz język który jest równy SAT, przecięty nieskończonym rozstrzygalnym rzadkim...

Dobrze znany problem SAT został tu zdefiniowany dla odniesienia. Problem DOUBLE-SAT jest zdefiniowany jako DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{...

Jaka jest złożoność MIN-2-XOR-SATMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} i MAX-2-XOR-SATMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? Czy są w P? Czy są twarde NP? Aby sformalizować to dokładniej, pozwól Φ(x)=∧niCi,Φ(x)=∧jandoja,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, gdzie...

Próbuję rozwiązać ten problem i naprawdę walczę. Monotoniczne logiczna wzór jest wzorem w zdań logiki, gdy wszystkie literałami dodatnie. Na przykład, ( x1∨ x2)) ∧ ( x1∨ x3)) ∧ ( x3)∨ x4∨ x5)(x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5) jest...