Złożoność sprawdzania, czy dwa CNF mają taką samą liczbę rozwiązań

Biorąc pod uwagę dwa CNF, jeśli mają taką samą liczbę zadań, aby były prawdziwe, odpowiedz „Tak”, w przeciwnym razie odpowiedz „Nie”.

Łatwo zauważyć, że jest to w , ponieważ jeśli znamy dokładną liczbę rozwiązań dla tych dwóch CNF, po prostu je kampanujemy i odpowiadamy „Tak” lub „Nie”. $P^{\#P}$

Jaka jest złożoność tego problemu?

cc.complexity-theory complexity-classes counting-complexity Mike Chen
źródło

Odpowiedzi:

Problemem jest coNP- twardy; możesz łatwo zredukować problem UNSAT do tego problemu.

Bardziej precyzyjną charakterystyką jest to, że problemem jest C ₌ P- zupełny. W rzeczywistości jedną z definicji klasy C ₌ P jest to, że jest to klasa problemów, które są wielomianowe w czasie wiele-jednym, które można zredukować do tego samego problemu (zwykle ta definicja jest wyrażona w funkcji GapP ). Ale ponieważ niewiele to mówi, pozwól mi zdefiniować tę klasę w inny sposób.

Niech C ₌ P będzie klasą problemów, które są wielomianowe w czasie wielomianowym, które można sprowadzić do następującego problemu: biorąc pod uwagę obwód logiczny φ i liczbę całkowitą K (binarnie), zdecyduj, czy liczba spełniających przypisań φ jest równa K . Dzięki standardowej redukcji, która pokazuje kompletność # P # 3SAT, możemy ograniczyć φ do formuły 3CNF bez wpływu na klasę. Klasa C ₌ P zawiera klasę o nazwie US , która zawiera zarówno UP, jak i coNP.

Przy tej definicji twój problem to C ₌ P-kompletny. W rzeczywistości twardość C ₌ P jest łatwa do zauważenia z definicji klasy C ₌ P (która wykorzystuje formuły 3CNF).

Aby udowodnić członkostwo w C ₌ P, załóżmy, że musimy zdecydować, czy dwie dane formuły CNF φ ₁ i φ ₂ mają taką samą liczbę zadowalających zadań, czy nie. Bez utraty ogólności możemy założyć, że dwie formuły mają tę samą liczbę zmiennych, powiedzmy n . Skonstruuj obwód logiczny φ, który przyjmuje n +1 bitów jako dane wejściowe, tak że liczba spełniających przypisań φ jest równa c ₁ + (2 ⁿ - c ₂ ), gdzie c ₁ i c ₂być liczbami spełniających zadania odpowiednio φ ₁ i φ ₂ . Wtedy liczba spełniających przypisań φ jest równa 2 ⁿ wtedy i tylko wtedy, gdy c ₁ = c ₂ .

Tsuyoshi Ito
źródło

@Kaveh: Czy możesz opracować?

Tsuyoshi Ito,

@Kaveh: Nie, nie tego chcemy. Chcemy zdecydować, czy φ_1 i φ_2 mają taką samą liczbę zadowalających zadań, niekoniecznie ten sam zestaw zadowalających zadań.

Tsuyoshi Ito,

@Tsuyoshi: Czy w oparciu o twoją definicję

, GI w

? I, że przynajmniej GI

C_{=} P

$C_=P$

C_{=} P

$C_=P$

\subseteq F P^{C_{=} P}

$\subseteq FP^{C_=P}$

Mike Chen

@ Mike: Dziękuję za interesujący komentarz. Mówisz co powoduje, że izomorfizm grafów ∈ SPP (Arvind i Kurur 2006 dx.doi.org/10.1016/j.ic.2006.02.002 )? Jeśli tak, masz rację; SPP zawarte w

, więc Graph Izomorfizm ∈

C_{=} P

$\mathrm{C}_=\mathrm{P}$

C_{=} P

$\mathrm{C}_=\mathrm{P}$

Tsuyoshi Ito,

@Mike: Dowiedziałem się, że przed wynikiem GraphIso∈SPP wiadomo było, że GraphIso ∈ LWPP : Köbler, Schöning i Torán 1992 . Od LWPP ⊆ WPP ⊆

, my nie potrzebujemy silniejszej wynik przez Arvind i Kurur powiedzieć, że GraphIso∈

C_{=} P

$\mathrm{C}_=\mathrm{P}$

C_{=} P

$\mathrm{C}_=\mathrm{P}$

Tsuyoshi Ito,

Oto niewielka odmiana pierwotnego pytania. Niech będzie wyrocznią, która na wejściu wyprowadza 1, jeśli CNF ma więcej rozwiązań niż CNF . $O$ $(f_1,f_2)$ $f_1$ $f_2$

Biorąc pod uwagę tę wyrocznię, budujemy maszynę która może rozwiązać # P-całkowity problem obliczania liczby rozwiązań dla danej CNF . Zauważ, że może mieć wykładniczą liczbę rozwiązań. $M$ $\varphi$ $\varphi$

działa w następujący sposób: Generuje formuł o znanej liczbie rozwiązań, a stosując przeszukiwanie binarne i zadając w większości wielomianowych zapytań do , to znajdzie formuły który mataką samąliczbę rozwiązań jak . W końcu wyświetla liczbę właśnie znalezionych rozwiązań. $M$ $O$ $\varphi_i$ $\varphi$

To pokazuje, że ma złożoność #p. $M^O$

MS Dousti
źródło

Wybacz moją niewiedzę, ale jak wygenerować formułę z określoną liczbą rozwiązań?

Giorgio Camerani

M = \sum_{i = 0}^{k} m_{i} 2^{i}

$M = \sum_{i=0}^k m_i 2^i$

S

$S$

i

$i$

m_{i} = 1

$m_i=1$

x_{0}, \dots, x_{k}

$x_0, \ldots, x_k$

y_{0}, \dots, y_{k}

$y_0, \ldots, y_k$

i \in S

$i \in S$

F_{i}

$F_i$

{x_{0}, \dots, x_{k - i}}

$\{x_0,\ldots,x_{k-i}\}$

{y_{0}, \dots, y_{k}}

$\{y_0, \ldots, y_k\}$

y_{i}

$y_i$

F_{i}

$F_i$

2^{i}

$2^i$

{x_{k - i + 1}, \dots, x_{k}}

$\{x_{k-i+1}, \ldots, x_k\}$ are free), and for

i \neq j

$i\ne j$ , the satisfying assignments of

F_{i}

$F_i$ and

F_{j}

$F_j$ are disjoint due to the

y

$y$ variables. The formula

\underset{i \in S}{⋁} F_{i}

$\bigvee_{i\in S} F_i$ has

M

$M$ satisfying assignments.

mikero

Note that it is PP-complete to decide whether, given two CNF formulas f_1 and f_2, f_1 has more satisfying assignments than f_2 or not.

Tsuyoshi Ito

@mikero: Ah, stupid me! I should have imagined that. Thanks for your illuminating explanation.

Giorgio Camerani

It seems like it's atleast NP-hard as one can easily construct a SAT formula with just one solution. Then by the Valiant-Vazirani theorem, there's a probabilistic reduction from every SAT formula to a set of Unique-SAT problems (determining whether a formula has a unique solution) and comparing those Unique-SAT problems with the constructed SAT formula with just one solution enables you to determine the satisfiability of the SAT formula under consideration.

Opt
źródło

To be precise, the first sentence should mention “under randomized reducibility” (although you mention it in the second sentence).

Tsuyoshi Ito