Dowód, że konwersja z CNF do DNF jest NP-trudna

20

Jak mogę udowodnić, że konwersja z CNF do DNF jest NP-trudna?

Nie proszę o odpowiedź, tylko kilka sugestii na temat tego, jak to udowodnić.

complexity-theory np-hard satisfiability sat-solvers normal-forms jkjk
źródło
5
W celu dogłębnej analizy zapoznaj się z tym artykułem „O konwersji CNF na DNF”
Vor
@ A. Schulz: oryginalna definicja w pracy Steve'a Cooka definiuje ją za pomocą redukcji Cooka. Wydaje się, że jest to redukcja stosowana przy omawianiu ogólnej twardości NP en.wikipedia.org/wiki/NP-hard
Kaveh
Konwersja CNF <-> DNF nie jest decyzją, ponieważ jest to język. jest to bardziej funkcja z wejściem i wyjściem i musi zostać przekonwertowana na problem decyzyjny, aby zapytać, czy w NP itp. uważa, że ​​udowodniono, że problem braku decyzji prowadzi do wykładniczego wzrostu wielkości [np. w Vors ref], dlatego NP pełna wersja problemu decyzyjnego [jeśli taki istnieje] jest prawdopodobnie znaczącym uproszczeniem. również jako Vors ref pokazuje rzeczywisty złożoności z CNF <-> konwersja DNF jest aktywnym problemem badawczym ... note istnieje pewne podobieństwo do wydajności algorytmu kompresji ...
vzn
2
@vzn Pytanie dotyczy tego, czy jest to NP- twardy, a nie NP -kompletny. Oznacza to, że członkostwo w NP nie jest wymagane, więc nie musi to stanowić problemu decyzyjnego.
David Richerby,

Odpowiedzi:

18

Nieprzepisowo:

W DNF możesz wybrać dowolną klauzulę, aby była prawdziwa, aby formuła była prawdziwa. Oznacza to, że DNF, który jest równoważny z pewną CNF, jest w zasadzie wyliczeniem wszystkich rozwiązań boolean na CNF. Uwaga: wykładnicza liczba rozwiązań może być wykładnicza. Ponieważ rozwiązywanie wartości logicznych dla CNF dla pojedynczego rozwiązania jest zakończone NP, konwersja do DNF zasadniczo oznacza rozwiązywanie każdego rozwiązania. Jest więc co najmniej tak trudny jak Boolean SAT, a zatem jest NP-trudny.

Realz Slaw
źródło