Pytania otagowane jako sat

SAT oznacza boolowski problem satysfakcji.

2
Czy obwody quasi-wielomianowe dla 3-SAT są banalne?
Załóżmy, że rozważamy 3-SAT ze zmiennymi i klauzulami c . Badam metodę, która wydaje się zajmować czas / przestrzeń O ( v 2 + log c ) w celu rozwiązania dowolnego problemu SAT pasującego do tego opisu, z błędem, który można dostosować do dowolnej kwoty. Jest jednak pewien haczyk.vvvdoccO ( …
3
Czy osadzenie rozwiązania jest możliwe dla SAT?
Interesują mnie „twarde” pojedyncze przypadki problemów z NP. Ryan Williams omówił problem SAT0 na blogu Richarda Liptona . SAT0 pyta, czy instancja SAT ma konkretne rozwiązanie składające się ze wszystkich zer. To skłoniło mnie do myślenia o konstruowaniu instancji SAT, które prawdopodobnie będą „trudne”. Rozważmy wystąpienie SAT z klauzulami i …
1
Zrozumienie wydajności solverów QFBV SMT
Solwery SMT, takie jak Z3 lub Boolector, wykorzystują złożony zestaw heurystyk do rozwiązywania problemów. Jednak bardzo utrudnia to przewidywanie wydajności takiego rozwiązania. Moje pytanie brzmi zatem: Pytanie Czy istnieje sposób na zrozumienie lub uzyskanie wglądu w wydajność solvera SMT dla konkretnego w teorii bitwektorów bez kwantyfikatora (QFBV)? Obejmuje to także …
1
Czy 1-w-3 SAT pozostaje NP-twardy, nawet jeśli każda zmienna występuje zarówno pozytywnie, jak i negatywnie?
Standardowy problem 1-w-3 SAT (lub XSAT lub X3SAT) to: Instancja : formuła CNF z każdą klauzulą ​​zawierającą dokładnie 3 literały Pytanie : czy istnieje zadowalające ustawienie przypisania dokładnie 1 literał na klauzulę prawda? Problem jest NP-zupełny i pozostaje trudny, nawet jeśli żadna zmienna nie zostanie zanegowana. Zastanawiam się, czy problem …
2
Przybliżenie problemów trudnych do # P
Rozważ klasyczny problem # P-zupełny nr 3SAT, tj. Policz liczbę wycen, aby uzyskać 3CNF z nnnzmienne zadowalające. Interesuje mnie przybliżalność addytywna . Najwyraźniej istnieje prosty algorytm do osiągnięcia2)n - 12n−12^{n-1}- błąd, ale jeśli k &lt;2)n - 1k&lt;2n−1k<2^{n-1}, czy można mieć skuteczny algorytm aproksymacyjny, czy ten problem jest również trudny do …
2
Ograniczona formuła Monotone 3CNF: liczenie spełniających się zadań (oba modulo
Rozważ formułę Monotone 3CNF mającą oba następujące dodatkowe ograniczenia: Każda zmienna występuje dokładnie w klauzulach.2)22 Biorąc pod uwagę dowolne klauzule, mają one maksymalnie zmienną.2)22111 Chciałbym wiedzieć, jak ciężko jest liczyć satysfakcjonujące zadania takiej formuły. Aktualizacja 06.04.2013 12:55 Chciałbym również wiedzieć, jak trudne jest ustalenie parytetu liczby satysfakcjonujących zadań. Aktualizacja 11.04.2013 …
2
Informacje o k-SAT (wprowadzenie, ograniczenia, metody itp.)
Chciałbym wiedzieć, gdzie mogę się zwrócić o dobre, delikatne wprowadzenie do k-SAT (może to być dla matematyków, którzy nie mają dobrego przygotowania informatycznego). Chciałbym również znać artykuły, które mogą przeglądać lub wyjaśniać obecne metody rozwiązywania k-SAT. Wreszcie interesują mnie najbardziej znane metody rozwiązywania k-SAT. Chciałbym dowiedzieć się, jaki jest najlepszy …
1
Jakieś sformułowania SAT / SMT VRP / VRPTW (TSP, Job-Shop-Scheduling)?
zastanawiam się, czy są jakieś podejścia do formułowania problemu trasy pojazdu z systemem Windows-Time ( VRPTW ) (jako problemem decyzyjnym) jako instancji SAT / SMT? (alternatywnie: TSP) Na przykład: „Czy istnieje prawidłowe rozwiązanie odwiedzające wszystkich klientów w ich ramach czasowych przy n = 10 pojazdach?” Ten problem decyzyjny może być …
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.