Czy znalezienie rozwiązania problemu satysfakcji jest trudniejsze niż podjęcie decyzji o satysfakcji?

11

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 zmiennych boolowskich? Czy też wszystkie możliwe dowody skracają czas wielomianu do „właściwych ustawień”?

Wybacz moją ignorancję, jestem tylko studentem inżynierii. Wikipedia wydaje się sugerować, że akt tylko rozpoznawczej SAT lub UNSAT jest NP-zupełny.

complexity-theory satisfiability

— Jason
źródło

8

Krótka odpowiedź: problem ze znalezieniem satysfakcjonującego zadania jest tak trudny obliczeniowo, jak podjęcie decyzji o jego istnieniu. Chodzi o to, że biorąc pod uwagę algorytm, który określa satysfakcję, można go wykorzystać do skutecznego skonstruowania satysfakcjonującego zadania. Sprawdź pl.wikipedia.org/wiki/...

— John D.

2

Myślałem, że UNSAT jest kompletny coNP?

— G. Bach

15

Jak wspomniano w komentarzu, każdą metodę określania satysfakcji wzoru logicznego można łatwo przekształcić w metodę znajdowania zadowalającego przypisania zmiennej. Wynika to z faktu, że wszystkie problemy związane z NP zakończone są w dół samoczynną redukcją.

Z Wikipedii :

Samonapędzalność

$Φ$ $Φ$ $\{x_1=TRUE\}$ $Φ$ $x_1$ $TRUE$ $x_1=TRUE$ $x_1=FALSE$ $n+1$ $n$ $Φ$

— Kyle Jones
źródło

-4

Prawidłowa odpowiedź jest taka, że ustalenie, czy rozwiązanie istnieje, i ustalenie rozwiązania są obliczeniowo różne. Nie wszystkie metody określania, czy istnieje rozwiązanie, mogą dać rozwiązanie. Istnieje rozwiązanie problemu ścieżki Hamiltonian, które może ustalić, czy ścieżka istnieje, ale nie może wytworzyć takiej ścieżki. To powiedziawszy, pytanie zostało zadane przez arxiv.org/abs/cs/0205064.

— Jerzy
źródło