Konwersja DNF do CNF: łatwa lub trudna

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 zainteresowani maksymalnym powiększeniem wielkości przy zmianie z reprezentacji CNF na reprezentację DNF (lub odwrotnie) ”.

Ale DNF-SAT jest w P, a CNF-SAT jest w stanie NP . Zatem biorąc pod uwagę wyrażenie DNF , powinno istnieć równoważne wyrażenie CNF którego długość jest wielomianowa o długości . A konwersję można wykonać w czasie wielokrotnym. Czy to jest poprawne? $\phi_1$ $\phi_2$ $\phi_1$ $\phi_1 \to \phi_2$

Edycja: Zmiana równoważne do equisatisfiable (to znaczy, innych zmiennych są dozwolone ). $\phi_2$

complexity-theory logic satisfiability normal-forms Martin Seymour
źródło

Możesz przejść z dowolnej formuły do CNF, co jest zadowalające dokładnie wtedy, gdy oryginalna formuła jest w czasie wielomianowym. Właśnie dlatego CNF-SAT jest kompletny NP. Każda instancja SAT (problem NP-zupełny) może zostać zredukowana do CNF-SAT w czasie wielomianowym. Myślę, że dokładne przetłumaczenie tego, nie tylko zachowanie satysfakcji, zawsze spowoduje wykładniczą eksplozję, ale nie mogę tego powiedzieć na pewno.

Jake

Zobacz en.wikipedia.org/wiki/Tseitin_transformation . Zasadniczo, jeśli zezwolisz na wprowadzenie zmiennych pomocniczych, możesz wykonać tę transformację w czasie wielozmiennym (zwiększając rozmiar formuły co najwyżej liniowo).

jschnei

Musisz zdecydować, czy chcesz zezwolić konwersji na wprowadzenie nowych zmiennych, czy przekonwertowana formuła musi odnosić się do tego samego zestawu zmiennych (bez nowych zmiennych). Jest to subtelny punkt, który ma dramatyczny wpływ na odpowiedź. Więc o co chcesz zapytać?

@Jake Możesz przejść z dowolnej formuły do niesatysfakcjonującej CNF, ponieważ CNF-SAT jest NP-kompletny. To nie jest tak naprawdę „dlaczego” CNF-SAT jest NP-zupełny: zwykły dowód, że CNF-SAT jest NP-zupełny, nie wymaga tłumaczenia arbitralnych wzorów na CNF; raczej przekłada maszyny Turinga na formuły CNF.

David Richerby,

Dla DW i innych - miałem na myśli równoważność . W tym sensie wydaje się, że równoważność jest tylko redukcją (w tym przypadku do innej formuły boolowskiej).

Martin Seymour,

Odpowiedzi:

Jeśli chcesz wprowadzić dodatkowe zmienne, możesz przekonwertować z postaci DNF do CNF w czasie wielomianowym za pomocą transformacji Tseitin . Otrzymana formuła CNF będzie w równym stopniu satysfakcjonująca z oryginalną formułą DNF: formuła CNF będzie zadowalająca wtedy i tylko wtedy, gdy oryginalna formuła DNF będzie zadowalająca. Zobacz także https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF .

Jeśli nie chcesz zezwalać na wprowadzanie dodatkowych zmiennych, konwersja z formatu DNF do CNF jest trudna dla NP. W szczególności testowanie, czy formuła DNF jest tautologią, jest trudne dla NP. Jednak sprawdzenie, czy formuła CNF jest tautologią, można przeprowadzić w czasie wielomianowym (wystarczy osobno sprawdzić, czy każda klauzula jest tautologią, co jest łatwe, ponieważ każda klauzula jest rozłączeniem literałów). Dlatego gdybyś mógł konwertować z postaci DNF do postaci CNF w czasie wielomianowym, bez wprowadzania nowych zmiennych, uzyskałby algorytm wielomianowy do testowania, czy formuła DNF jest tautologią - co wydaje się mało prawdopodobne, biorąc pod uwagę, że oczekujemy P nie jest równy co-NP. Innymi słowy, konwersja z formatu DNF do CNF bez wprowadzania dodatkowych zmiennych jest trudna dla NP.

Jest to różnica pomiędzy równoważności vs equisatisfiability . Równoważność wymaga, aby te dwie formuły miały ten sam zestaw rozwiązań (a zatem nie pozwalają na wprowadzenie dodatkowych zmiennych). Zgodność wymaga tylko, aby obie formuły były zadowalające lub obie były niezadowalające (a zatem umożliwia wprowadzenie dodatkowych zmiennych).

DW
źródło

@ Mehrdad, nie używaj komentarzy do zadawania nowych pytań. W prawym górnym rogu mamy „Zadaj pytanie”, jeśli masz nowe pytanie, które chcesz zadać. Ale, tylko mała wskazówka ... możesz przeczytać pytanie na górze tej strony przed zadaniem nowego pytania ... lub, jeśli o to chodzi, opublikowaniem tego komentarza. Nie mogę nie zauważyć, że zadałeś pytanie, na które odpowiedź znajduje się na tej samej stronie co twoje pytanie.

@DW: Ups, trochę później zobaczyłem ten drugi post i przepraszam, że zapomniałem usunąć tutaj swój komentarz. Usunąłem to teraz.

user541686,