To chyba głupie pytanie, ale po prostu nie rozumiem. W kolejnym pytaniu wymyślili dychotomia twierdzenia Schaefer jest . Dla mnie wygląda na to, że udowadnia, że każdy problem CSP jest w P lub NP-kompletny, ale nie pomiędzy. Skoro każdy problem NP można przekształcić w czasie wielomianowym w CSP...
Widziałem, w jaki sposób XOR-3-SAT można skutecznie rozwiązać (na przykład zobacz sekcję „Zgodność XOR” we wpisie w Wikipedii na temat problemu logicznej satysfakcji ). Zastanawiam się nad podstawowym pytaniem: czy XOR-k-SAT można skutecznie rozwiązać w przypadku formuł o różnej ilości literałów...
Problem decyzyjny Biorąc pod uwagę logiczną formułę , czy ϕ ma dokładnie jedno zadowalające zadanie?ϕϕ\phiϕϕ\phi mogą być widoczne w , U P -hard i c o N P -hard. Czy jest coś bardziej znanego na temat jego
Czy problem polegający na ustaleniu, czy dane wyrażenie logiczne jest zadowalające obliczeniowo, różni się od znalezienia rozwiązania dla wyrażenia? Innymi słowy, czy istnieje inny sposób stwierdzenia, że dane wyrażenie jest zadowalające bez wyraźnego określenia „właściwych ustawień” dla...
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then { T;...
Nowoczesne solwery SAT bardzo dobrze rozwiązują wiele rzeczywistych przykładów instancji SAT. Wiemy jednak, jak generować trudne: na przykład użyj redukcji z faktoringu do SAT i podaj liczby RSA jako dane wejściowe. Rodzi to pytanie: co jeśli wezmę prosty przykład faktoringu. Zamiast brać dwóch...
Zastanawiam się, czy istnieje algorytm wielomianowy dla „2-SAT z relacjami XOR”. Zarówno 2-SAT, jak i XOR-SAT są w P, ale czy jest to kombinacja? Przykładowe dane wejściowe: Część 2-SAT: (a or !b) and (b or c) and (b or d) Część XOR: (a xor b xor c xor 1) and (b xor c xor d) Innymi słowy,...
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...
W odniesieniu do wątku Udowodnienie, że konwersja z CNF do DNF jest NP-twarda (i powiązany wątek matematyczny ): Co powiesz na inny kierunek, od DNF do CNF? Czy to jest łatwe czy trudne? Na stronie 2 tego artykułu wydają się sugerować, że oba kierunki są równie trudne, gdy mówią: „ Jesteśmy...
Jestem absolwentem liceum, który interesuje się informatyką. Opracowałem fajny algorytm dla #SAT i wdrażam na nim projekt Science Fair. Mój doradca, który jest najlepszym nauczycielem przedmiotów ścisłych w mojej szkole i nauczycielem AP Comp Sci, powiedział mi, że absolutnie nie ma pojęcia, o czym...
Na stronie wikipedia tutaj całkiem dobrze opisuje algorytm CDCL (i wydaje się, że zdjęcia zostały zrobione ze slajdów stworzonych przez Sharada Malika z Princeton). Jednak przy opisywaniu sposobu cofania wszystko mówi „do właściwego punktu”. MiniSAT wykorzystuje również wariant algorytmu CDCL, więc...
Valiant i Vazirani udowodnili, że SAT można zredukować do UNIKALNEGO SAT przy randomizowanych probabilistycznych redukcjach czasu wielomianowego. Calabro i in . pokazał, że UNIKALNY k-SAT jest tak trudny jak k-SAT. Teraz pytanie brzmi: jeśli ktoś pokaże, że UNIKALNY k-SAT jest w P, czy oznacza to,...
Zastanawiałem się, czy ten problem ma nazwę: Biorąc pod uwagę prosty wykres, którego krawędzie są w kolorze czerwonym, niebieskim i zielonym, G = ( V, B ∪ R ∪ G )G=(V,B∪R∪G)G=(V,B\cup R\cup G), czy jest kolorowanie wierzchołków c : V→ { B , R , G }c:V→{B,R,G}c:V\to \{B,R,G\} tak, że każda krawędź...
Niech będzie językiem wszystkich formuł -CNF , tak aby przynajmniej z klauzul mogły być spełnione.LϵLϵL_\epsilon222φφ\varphi(12+ϵ)(12+ϵ)(\frac{1}{2}+\epsilon)φφ\varphi Muszę udowodnić, że istnieje st is twardy dla każdego