Pytania otagowane jako 3-sat

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 <- …
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?
1
Warunki płaskości dla Planar 1-in-3 SAT
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 (xi,xi¯)(xi,xi¯)(x_i,\bar{x_i}) dodaj krawędź z wierzchołka (lub ¯ x i ) do …
1
Jak udowodnić, że ograniczona wersja 3SAT, w której dosłowność nie może wystąpić więcej niż jeden raz, można rozwiązać w czasie wielomianowym?
Próbuję wypracować zadanie (zaczerpnięte z książki Algorytmy - S. Dasgupta, CH Papadimitriou i UV Vazirani , Rozdział 8, problem 8.6a), i parafrazuję to, co mówi: Biorąc pod uwagę, że 3SAT pozostaje NP-kompletny, nawet jeśli ogranicza się do formuł, w których każdy literał pojawia się co najwyżej dwa razy, pokaż, że …
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.