Сложность проверки, имеют ли два CNF одинаковое количество решений

Учитывая два CNF, если они имеют одинаковое количество назначений, чтобы сделать их правдой, ответьте «Да», в противном случае ответьте «Нет».

Легко увидеть, что это в $P^{\#P}$ , поскольку, если мы знаем точное число решений этих двух CNF, мы просто собираем их и отвечаем «Да» или «Нет».

В чем сложность этой проблемы?

cc.complexity-theory complexity-classes counting-complexity Майк Чен
источник

Ответы:

Проблема в том, что coNP -hard; Вы можете легко свести проблему UNSAT к этой проблеме.

Более точная характеристика заключается в том, что проблема в C ₌ P -полном. На самом деле, одно из определений класса C ₌ P состоит в том, что это класс задач, многокритериальный за многочленовое время, сводимый к этой самой проблеме (обычно это определение формулируется в терминах функций GapP ). Но так как это не говорит о многом, позвольте мне определить этот класс по-другому.

Пусть C ₌ P будет классом задач, которые многозначно за многочленное время сводятся к следующей задаче: с учетом булевой схемы φ и целого числа K (в двоичном виде) решить, равно ли число удовлетворяющих назначений φ равен K , Стандартным сокращением, которое показывает # P-полноту # 3SAT, мы можем ограничить φ формулой 3CNF, не влияя на класс. Класс C ₌ P содержит класс с именем US , который содержит как UP, так и coNP.

С этим определением ваша проблема является C ₌ P-полной. На самом деле, твердость C ₌ P легко увидеть из определения класса C ₌ P (который использует формулы 3CNF).

Чтобы доказать членство в C ₌ P, предположим, что мы должны решить, имеют ли две данные формулы CNF φ ₁ и φ ₂ одинаковое число удовлетворяющих присвоений или нет. Без ограничения общности мы можем предположить, что две формулы имеют одинаковое количество переменных, скажем, n . Построить логическую схему φ, которая принимает n + 1 бит в качестве входных данных, чтобы число удовлетворяющих присвоений φ было равно c ₁ + (2 ⁿ - c ₂ ), где c ₁ и c ₂быть числами удовлетворяющих присвоений φ ₁ и φ ₂ , соответственно. Тогда число удовлетворяющих отведений φ равно 2 ⁿ тогда и только тогда, когда c ₁ = c ₂ .

Цуёси Ито
источник

@Kaveh: Можете ли вы уточнить?

Цуёси Ито

@Kaveh: Нет, это не то, что мы хотим. Мы хотим решить, имеют ли φ_1 и φ_2 одинаковое количество удовлетворяющих назначений, а не обязательно один и тот же набор удовлетворяющих назначений.

Цуёси Ито

@ Tsuyoshi: На основании вашего определения

, GI в

? Я думаю , что по крайней мере GI

C_{=} P

$C_=P$

C_{=} P

$C_=P$

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

$\subseteq FP^{C_=P}$

Майк Чен

@Mike: Спасибо за интересный комментарий. Вы говорите о результате этого изоморфизма графов SPP (Арвинд и Курур 2006 dx.doi.org/10.1016/j.ic.2006.02.002 )? Если это так, вы правы; SPP содержится в

, так что изоморфизм графов ∈

C_{=} P

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

C_{=} P

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

Цуёси Ито

@Mike: я узнал, что перед результатом GraphIso∈SPP было известно, что GraphIso ∈ LWPP : Köbler, Schöning и Torán 1992 . Поскольку LWPP ⊆ WPP ⊆

, мы не нуждались в более сильный результат, Арвинд и Kurur сказать , что GraphIso∈

C_{=} P

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

C_{=} P

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

Цуёси Ито

Вот небольшая вариация на оригинальный вопрос. Пусть - оракул, который на входе выдает 1, если CNF имеет больше решений, чем CNF . $O$ $(f_1,f_2)$ $f_1$ $f_2$

Учитывая этот оракул, мы строим многовременную машину которая может решить # P-полную задачу вычисления числа решений для данного CNF . Заметим, что может иметь экспоненциальное число решений. $M$ $\varphi$ $\varphi$

работает следующим образом: он генерирует формулы с известным числом решений и, используя бинарный поиск и, задавая большинство полиномиальных запросов к , находит формулы которые имеютто жечисло решений, что и . Наконец, выводится количество только что найденных решений. $M$ $O$ $\varphi_i$ $\varphi$

Это показывает, что имеет сложность #P. $M^O$

М.С. Дусти
источник

Простите мое невежество, но как вы генерируете формулу с заранее определенным количеством решений?

Джорджио Камерани

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}\}$ are true AND among

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

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

y_{i}

$y_i$ is true."

F_{i}

$F_i$ has

2^{i}

$2^i$ satisfying assignments (the variables

{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
источник

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

Tsuyoshi Ito