Unikalne modele SAT vs Dokładnie

Unikalny SAT jest dobrze znanym problemem: biorąc pod uwagę wzór CNF , czy to prawda, że ma dokładnie jeden model? $F$ $F$

Interesuje mnie problem «Dokładnie SAT»: biorąc pod uwagę wzór CNF i liczbę całkowitą , czy to prawda, że ma dokładnie modeli? $m$ $F$ $m>1$ $F$ $m$

Oba problemy wyglądają podobnie. Więc moje pytania to:

1- Czy polytime «Dokładnie SAT» (wiele-jeden lub Turing) można zredukować do Unikalnego SAT? $m$

2- Czy znasz jakieś odniesienia na ten temat?

Dziękuję Ci za Twoje odpowiedzi.

Dodatek , pierwsze artykuły o złożoności programu Dokładnie SAT: $m$

1- Janos Simon, O różnicy między jednym a wieloma, w toku czwartego kolokwium na temat automatów, języków i programowania, 480-491, 1977.

2- Klaus W. Wagner, Złożoność problemów kombinatorycznych z zwięzłą reprezentacją danych wejściowych, Acta Informatica, 23, 325-356, 1986.

W obu artykułach pokazane jest , że Dokładnie SAT ( ) to całkowite (przy wielu redukcjach jeden), gdzie klasa pochodzi z Hierarchii Liczenia (CH) klas złożoności. Nieformalnie zawiera wszystkie problemy, które można wyrazić, decydując, czy dana instancja ma co najmniej wielu wielomianowych dowodów wielkości ( wiadomo, że klasa pokrywa się z klasą ). Klasa jest wariantem , gdzie „dokładnie ” zastępuje „co najmniej ”. $m$ $m \geq 1$ $C=$ $C$ $C$ $m$ $C$ $PP$ $C=$ $C$ $m$ $m$

— Xavier Labouze
źródło

To redukcja czasu Turinga: znajdź rozwiązanie, dodaj klauzulę eliminującą go i powtarzaj, aż formuła stanie się niezadowalająca.

— Kaveh

1. urządzenie poda liczbę rozwiązań lub ma więcej niż

rozwiązań. 2. Możesz dodać negację koniunkcji opisującą rozwiązanie.

m

$m$

— Kaveh

Jeśli nie znasz związku między PP a liczeniem liczby rozwiązań, sprawdź podręcznik dotyczący teorii złożoności, taki jak Papadimitriou.

— Tsuyoshi Ito

(1) Jeśli m jest wielomianowo ograniczone, twoim problemem jest wielomianowy czas wielokrotny, który można zredukować do Unique SAT, traktując listę m rozwiązań posortowanych w porządku leksykograficznym jako pojedynczy certyfikat. (2) Proszę nie brać mojej odpowiedzi za dowód, że zadałeś pytanie we właściwym miejscu. Myślę, że to konkretne pytanie znajduje się na granicy między tematem a tematem nie na temat. Naprawdę powinieneś rozważyć zadawanie pytań w innym miejscu.

— Tsuyoshi Ito,

Chociaż oświadczasz, że m jest ograniczone wielomianowo, niektóre stwierdzenia w pytaniu wymagają, aby m był arbitralny i nie będzie już obowiązywał, jeśli ograniczysz m, aby był ograniczony wielomianowo. Musisz zrozumieć, o czym mówisz, zanim zadasz spójne pytanie. Właśnie dlatego nie chcę zamieszczać odpowiedzi na to pytanie tutaj, gdzie pytania powinny być na poziomie badawczym.

— Tsuyoshi Ito,

$m$

— Noam
źródło

m

$m$

n

$n$

m

$m$

m

$m$

m = 2^{O (n)}

$m= 2^{O(n)}$

m

$m$

m

$m$

Duże m wciąż nie umieszcza problemu w P. Post aktualizacji jest niepoprawny, ponieważ stwierdzenie, że dokładnie-k-sat to C = P-zupełne, jest prawdziwe, gdy k jest częścią danych wejściowych, a zatem redukcja do k / 2 -sat nie ma sensu.

— Noam

m

$m$

m

$m$

y_{1}, y_{2} \dots y_{m}

$y_1,y_2 \cdots y_m$

F^{'} = F \land y_{1} \land y_{2} \land \dots \land y_{m}

$F'=F\land y_1 \land y_2 \land \cdots \land y_m$

F^{'}

$F'$

F

$F$

m

$m$

F^{'}

$F'$

F^{'}

$F'$

F^{'}

$F'$

F

$F$

m

$m$

| F |

$|F|$