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