Wariant Critical SAT w DP

Język jest w klasie iff istnieją dwa języki i tak że $L$ $DP$ $L1 \in NP$ $L2 \in coNP$ $L = L1 \cap L2$

Kanonicznym problemem z dopełnieniem $DP$ jest SAT-UNSAT: biorąc pod uwagę dwa wyrażenia 3-CNF, $F$ i $G$ , czy to prawda, że $F$ jest zadowalający, a $G$ nie?

Krytyczny problem SAT jest również znany jako kompletny $DP$ : Czy biorąc pod uwagę wyrażenie 3-CNF $F$ , to prawda, że $F$ jest niezadowalający, ale usunięcie jakiejkolwiek klauzuli powoduje, że jest zadowalające?

Rozważam następujący wariant Krytycznego problemu SAT: Biorąc pod uwagę wyrażenie 3-CNF $F$ , czy to prawda, że $F$ jest zadowalające, ale dodanie jakiejkolwiek klauzuli 3 (z $F$ ale przy użyciu tych samych zmiennych co $F$ ) czyni go niezadowalającym? Ale nie udało mi się znaleźć redukcji z SAT-UNSAT, ani nawet udowodnić, że jest to trudna $NP$ lub $coNP$ .

Moje pytanie: czy ten wariant DP jest kompletny?

Dziękuję Ci za Twoje odpowiedzi.

cc.complexity-theory np-hardness complexity-classes sat Xavier Labouze
źródło

Nie wiedziałem o DP: interesująca klasa, szczególnie jeśli CRITICAL-SAT jest na to gotowy.

Suresh Venkat,

Jeśli istnieją dwa zadowalające zadania , to nie jest maksymalne. (załóżmy, że różnią się one dla zmiennej , a następnie nie jest sugerowane przez formułę i dodanie jej lub klauzula zawierająca go nie zmieni satysfakcji.) Jeśli znajdziemy klauzulę nie sugerowaną przez formułę w czasie wielomianowym, możemy dodać jej negacja formuły i użycie reguły klauzuli jednostkowej. W końcu znajdziemy wartość wszystkich zmiennych dla satysfakcjonującego przypisania. Następnie musimy tylko sprawdzić, czy formuła jest równoważna formule kanonicznej dla tego zadania.

τ \neq τ^{'} ⊨ φ

$\tau\neq\tau' \vDash \varphi$

φ

$\varphi$

p

$p$

p

$p$

Kaveh

@Kaveh: Źle zrozumiałem twoje wyrafinowane pytanie. W twojej wersji pytania „nie ma klauzuli, która nie wynika z formuły i może być dodana do niej bez powodowania, że jest niespełniana” jest równoznaczna z warunkiem, że jest dokładnie jedno zadowalające zadanie i jest to standardowe US - kompletny (stąd trudny coNP) problem.

Tsuyoshi Ito,

Xavier: Masz rację, ponieważ język w wersji @ Kaveha jest podzbiorem języka w twojej wersji. Ale to nie oznacza redukcji między dwoma problemami (w obu kierunkach). Pamiętaj, że redukcja musi odwzorować instancje tak na instancje tak, a instancje nie na instancje nie.

Tsuyoshi Ito,

Przepraszam, pisałem w przeciwnym kierunku. Język w twojej wersji jest podzbiorem języka w wersji Kaveha.

Tsuyoshi Ito,

Odpowiedzi:

[Uczyniłem z tego poprawną odpowiedź b / c ktoś jej dał -1]

Jeśli dozwolone jest dodanie dowolnej klauzuli, wówczas język jest pusty - wyraźnie do dowolnej zadowalającej formuły można dodać 3-klauzulę złożoną ze zmiennych, które nie pojawiają się w : będzie być zadowalającym. $F$ $c$ $F$ $F \cup \{ c \}$

Jeśli dodane klauzule muszą używać zmiennych , wówczas językiem jest P. $F$

Uzasadnienie jest następujące:

Weź dowolne , tj. i dla każdej 3-klauzuli na zmiennych , . Powiedz , gdzie jest dosłowne. Ponieważ ma wartość UNSAT, wszystkie modele muszą mieć (dla ) - ponieważ jeśli jakiś model miał np. , wówczas spełniałby a więc . Załóżmy teraz, że istnieje inna klauzula która jest dokładnie jak $F \in L$ $F \in SAT$ $c$ $F$ $F \cup \{c\} \in UNSAT$ $c = l_1 \lor l_2 \lor l_3 \notin F$ $l_i$ $F \cup \{ c \}$ $F$ $l_i=0$ $i=1,2,3$ $l_1=1$ $c$ $F \cup \{c\}$ $c'$ $c$ , ale z jednym lub kilkoma dosłownymi odwróceniami i takimi, że , powiedzmy . Zatem tym samym argumentem wszystkie modele muszą mieć . Zatem warunkiem koniecznym dla jest to, że dla każdego punktu są dokładnie 6 pozostałe klauzule , które korzystają z tych trzech zmiennych - pozwala nazwać te podzbiory 7-klauzula bloków . Zauważ, że każdy blok implikuje unikalne, satysfakcjonujące przypisanie do swoich zmiennych. Gdy ten konieczny warunek jest spełniony, $c' \notin F$ $c' = \neg l_1 \lor l_2 \lor l_3$ $F$ $l_1 = 1$ $F \in L$ $c \in F$ $F$ $c$ $F$ $F$ jest wyjątkowo zadowalające lub niezadowalające. Oba przypadki można rozróżnić, sprawdzając, czy przypisania implikowane przez bloki zderzają się, co można wyraźnie wykonać w czasie liniowym. $F$

Anton Belov
źródło

Twoja obserwacja jest w zasadzie: aby uzyskać odpowiedź Tak, F musi zawierać dokładnie siedem z ośmiu klauzul dotyczących dowolnego wyboru trzech różnych zmiennych. Dlatego znalezienie unikalnego przypisania (lub wykrycie niespójności) jest łatwe do wykonania w czasie wielomianowym.

Tsuyoshi Ito,

@Xavier: Dwa problemy mogą wyglądać podobnie, ale obserwacja Antona pokazuje, że są one po prostu bardzo różne. Jest to bardzo powszechne w złożoności obliczeniowej. Typowe przykłady obejmują porównanie 2SAT i 3SAT oraz między obwodem Eulera a obwodem hamiltonowskim.

Tsuyoshi Ito,

@Xavier - odpowiedź Tayfuna jest niepoprawna . Pokazuje, że problem występuje w DP - w porządku, każdy problem w P występuje automatycznie w DP. Aby pokazać, że problem dotyczy DP-complete, musi wykazać redukcję do innego problemu z DP-zupełnym (np. Pierwszym wariantem Krytycznego SAT). Przesłałem poprawkę do jego odpowiedzi, ale jest ona w kolejce do „recenzji”.

Anton Belov

@Anton: drastycznie nie zaleca się edytowania odpowiedzi opublikowanych przez innych użytkowników. Jeśli uważasz, że odpowiedź Tayfun jest zasadniczo niepoprawna, nie powinieneś próbować jej naprawiać poprzez edycję.

Tsuyoshi Ito,

Z problemu SAT-UNSAT jasno wynika, że w przypadku jednej formuły sprawdzana jest satysfakcja w przypadku drugiej formuły, w której sprawdzana jest niespełnialność ... W pierwotnym krytycznym problemie sat nie bierze się za pewnik, że dana formuła boolowska jest niezadowalająca. Musisz to sprawdzić. Podobnie z wersją Xaviers, musisz sprawdzić, czy podana formuła boolowska jest zadowalająca.

Tayfun Zapłać

-1

Czy mogę zaproponować odpowiedź na moje pytanie dzięki waszym komentarzom: wariant Krytycznej SAT znajduje się w P.

Nazwijmy „Problem 1” wariantem Critical SAT: Biorąc pod uwagę wyrażenie 3-CNF , czy to prawda, że jest zadowalające, ale dodanie jakiejkolwiek klauzuli z czyni go niezadowalającym? $F$ $F$ $F$

I „Problem 2”: Biorąc pod uwagę wyrażenie 3-CNF , czy to prawda, że zawiera wszystkie zawarte w nim klauzule i ma unikalny model? $F$ $F$

Biorąc pod uwagę wzór 3-CNF, . $F$

Jeśli jest przykładem tak problemu 2, to każdy z klauzuli nie jest zastosowana przez i obejmuje tylko jeden z możliwych spełniającą zadanie dla . Dodanie takiej klauzuli do czyni ją niestabilną. jest w konsekwencji tak przypadkiem problemu 1. $F$ $F$ $F$ $F$ $F$ $F$

Jeśli jest przykładem bez problemu 2, a następnie: Przypadek 1: to istnieje zapis OUT , który jest w sposób dorozumiany przez . Dodanie tej klauzuli do nie zmienia jej satysfakcji. związku z tym nie powoduje wystąpienia problemu 1. Przypadek 2: zawiera wszystkie wynikające z tego klauzule, ale jest niezadowalający. związku z tym nie powoduje wystąpienia problemu 1. Przypadek 3: zawiera wszystkie wynikające z niego klauzule, ale ma co najmniej 2 różne modele. Jak podkreśla komentarz Kaveha, «zakładamy, że modele różnią się zmienną p, a dodanie klauzuli, która ją zawiera, nie zmieni satysfakcji. »W konsekwencji nie jest przypadkiem problemu 1. $F$ $F$ $F$ $F$ $F$ $F$ $F$ $F$ $F$

Zatem to tak wystąpienie problemu 1 iff to tak wystąpienie problemu 2. $F$ $F$

Problem 2 jest wyraźnie problemem P (na przykład jest tak wystąpieniem problemu 2 iff dokładnie tam są = zdania z F bez żadnych przeciwnych literałów w dwóch dowolnych z nich - to liczba zmiennych). Podobnie jest z problemem 1. $F$ $\binom{n}{3}$ $\frac{n(n-1)(n-2)}{3}$ $n$

Xavier Labouze
źródło

Przeredagowałeś oryginalny problem według własnych upodobań.

Tayfun Zapłać

Nie jestem pewien co do wersji 3-SAT. Biorąc pod uwagę formułę boolowską w CNF z klauzulami M i zmienną N, JEŻELI M = (3 ^ N) - (2 ^ N), wówczas podana formuła boolowska jest NIEODZIELNA lub ma tylko JEDNE Rozwiązanie. Mimo to sprawdzanie satysfakcji w tym przypadku jest nadal NP. Nie ma mowy, że Twoja wersja jest w P.

Tayfun Pay

@Xavier: Ta odpowiedź wydaje się poprawna, ale myślę, że jest taka sama jak to, co robi Anton w swojej odpowiedzi.

Tsuyoshi Ito,

@Tsuyoshi, masz rację, właśnie przedstawiam Problem 2, którego pierwsza część (testowanie, czy formuła zawiera wszystkie zawarte w nim klauzule) mnie interesuje - nawiasem mówiąc, czy masz pojęcie o złożoności tej pierwszej części?

Xavier Labouze