Сложность вычисления четности для чтения дважды противоположной формулы КНФА (

В противоположной формуле CNF с двойным чтением каждая переменная появляется дважды, один раз положительный и один раз отрицательный.

Меня интересует проблема , которая заключается в вычислении четности числа удовлетворяющих назначений противоположной формуле CNF с . $\oplus\text{Rtw-Opp-CNF}$

Я не смог найти никаких ссылок на сложность такой проблемы. Самым близким, что мне удалось найти, является то, что версия является -complete (см. Раздел 6.3 в этой статье ). $\#\text{Rtw-Opp-CNF}$ $\#\text{P}$

Заранее спасибо за вашу помощь.

Обновление 10 апреля 2016

В данной работе , то Проблема Показано, что -полным, однако формула получают восстановлением из не находится в КНФ, и как только вы попытаетесь преобразовать его обратно в CNF, вы получите формулу для чтения трижды. $\oplus\text{Rtw-Opp-SAT}$ $\oplus\text{P}$ $3\text{SAT}$
Показано, что монотонная версия является -полной в этой статье . В такой статье быстро упоминается в конце раздела 4: Valiant говорит, что он вырожден. Мне не ясно, что именно означает вырождение, и что это означает с точки зрения твердости. $\oplus\text{Rtw-Mon-CNF}$ $\oplus\text{P}$ $\oplus\text{Rtw-Opp-CNF}$

Обновление 12 апреля 2016

Было бы также очень интересно узнать, изучал ли кто-нибудь всю сложность проблемы . При заданной противоположной формуле CNF с двойным чтением такая задача требует вычислить разницу между количеством удовлетворяющих назначений, для которых нечетное число переменных установлено в значение true, и числом удовлетворяющих назначений, в которых четное число переменных установлено в значение true. Я не нашел никакой литературы об этом. $\Delta\text{Rtw-Opp-CNF}$

Обновление 29 мая 2016

Как отметил Эмиль Йержабек в своем комментарии, неправда, что Валиант сказал, что проблема вырождена. Он только сказал, что более ограниченная версия такой проблемы, , является вырожденной. Между тем, я продолжаю не знать, что именно означает дегенерат, но, по крайней мере, теперь кажется очевидным, что это синоним отсутствия выразительной силы. $\oplus\text{Rtw-Opp-CNF}$ $\oplus\text{Pl-Rtw-Opp-3CNF}$

cc.complexity-theory ds.algorithms counting-complexity Джорджио Камерани
источник

TRtw-Opp-CNF такой же твердый, как ⊕Rtw-Mon-CNF. Вы можете создать гаджет отрицания: (i0 v x0 v x1) (x1 v x2) (i1 v x0 v x2). Если i0 = i1, то вес = 0 (по модулю 2). В противном случае вес = 1.

Я не могу найти сокращение от tRtw-Mon-CNF до ⊕Rtw-Opp-CNF, но я нашел полиномиальный алгоритм для решения ⊕Rtw-Opp-CNF. Так что ⊕Rtw-Opp-CNF проще.

Я не могу найти упоминание ⊕Rtw-Opp-CNF в газете Валианта. Он утверждает, что lPl-Rtw-Opp-3CNF является «вырожденным», но это включает несколько дополнительных ограничений.

Эмиль Йержабек

@ EmilJeřábek: Вы определенно правы. Я был введен в заблуждение своим незнанием значения «вырожденный» , и я применил тот же тип рассуждений, который обычно применяется при наличии результатов полноты: если определенная задача полна для некоторого класса, удаление из него ограничений, очевидно, сохраняет полноту. Даже если я до сих пор не знаю, что именно означает «вырожденный» , мне, по крайней мере, теперь ясно, что такой термин как-то является синонимом слабости (т.е. отсутствия выразительной силы), поэтому вышеупомянутые рассуждения не могут быть применены. Я исправил вопрос соответственно.

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

@Maciej: Действительно? Как работает ваш полиномиальный алгоритм?

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

Ответы:

Оказывается, что каждая формула с противоположным чтением имеет четное число удовлетворяющих заданий. Вот хорошее доказательство этого, хотя, возможно, можно было бы исключить теоретико-графическую терминологию.

Пусть - формула CNF с обратным чтением, дважды. Без ограничения общности ни одно предложение не содержит ни переменной, ни ее отрицания. $\phi$

Рассмотрим граф которого множество вершин являются предложениями , и для каждой переменной мы добавляем (неориентированное) ребро, которое падает на два предложения, содержащие . Наше предположение WLOG в говорит, что этот граф не имеет самоконтролей. Кроме того, подумайте о маркировке каждого ребра переменной, определяющей его; таким образом мы можем различить параллельные ребра. $G$ $\phi$ $x$ $x$ $\phi$

Ориентации представляет собой ориентированный граф, ребра которого образованы путем присвоения направление каждого ребра в . Назовем ориентацию допустимой, если каждая вершина имеет исходящее ребро. Легко видеть , что удовлетворяющие присвоения в взаимно однозначном соответствии с допустимыми ориентациями . $G$ $G$ $G$ $G$ $\phi$ $G$

Теперь я утверждаю, что число допустимых ориентаций группы четно. Аргумент «инволюция»: Я построить отображение со следующими свойствами: $G$ $\Phi$

полностью определено (каждая допустимая ориентация где-то отображается) $\Phi$
отправляет допустимые ориентации в допустимые ориентации $\Phi$
- инволюция ( - тождество) $\Phi$ $\Phi \circ \Phi$
не имеет фиксированных точек $\Phi$

После того, как они установлены, мы можем наблюдать , что орбиты имеют размер 2 и разделить допустимые ориентации . Отсюда следует, что число допустимых ориентаций четное. $\Phi$ $G$

Чтобы определить , пусть - допустимая ориентация и рассмотрим разбиение на его сильно связные компоненты. затем отправляет в ориентацию, образованную путем обращения всех ребер в сильно связанных компонентах. Свойства затем проверяются напрямую: $\Phi$ $\vec{G}$ $\vec{G}$ $\Phi$ $\vec{G}$

Каждый ориентированный граф можно разбить на сильно связные компоненты.
Рассмотрим «DAG сильно связных компонент» в ; назовите это фактор-граф. Заметим, что будет иметь одинаковую фактор-структуру, поскольку не влияет на ребра между SCC, а сильно связанные графы остаются сильно связными при обращении всех своих ребер. Кроме того, если SCC имеет более одной вершины, то все составляющие вершины имеют входящее ребро. Если SCC имеет только одну вершину и не является источником в частном, то все его составляющие вершины имеют входящее ребро. Таким образом, чтобы показать $\vec G$ $\Phi(\vec G)$ $\Phi$ $\Phi(\vec G)$ допустимо, достаточно показать, что SCC, являющиеся источниками в частном, имеют несколько вершин. Но это следует из того факта, что каждая вершина в компоненте имеет входящее ребро, которое должно исходить из другой вершины в компоненте, так как не имеет собственных петель, а компонент является источником в частном. $G$
Это следует из того факта , что фактор - структура совпадает с фактор - структурой . $\Phi(\vec G)$ $\vec G$
По допустимости, имеет цикл и, следовательно, некоторый SCC с ребром внутри. $\vec G$

Эндрю Морган
источник

Хорошее наблюдение! Более простой способ увидеть это (как вы говорите, «исключить теоретико-графическую терминологию») состоит в том, чтобы наблюдать, что если присваивание a удовлетворяет F, то присваивание a '(x) = 1-a (x) также удовлетворяет F. Это можно легко показать по индукции по числу переменных Ф.

Холф

Я не думаю, что

как данность является инволюцией. Например, рассмотрим 4-элементный граф с направленными ребрами

. Это допустимая ориентация. Предположим, что его первый цикл

; затем, после изменения этого цикла, новый цикл возникает, а именно.

. Если этот цикл упорядочен до исходного, у нас проблемы.

Φ

$\Phi$

0 \to 1 \to 2 \to 0 \to 3 \to 1

$0\to1\to2\to0\to3\to1$

0 \to 1 \to 2 \to 0

$0\to1\to2\to0$

0 \to 3 \to 1 \to 0

$0\to3\to1\to0$

Эмиль Йержабек

@holf Ваше наблюдение тоже неверно. Рассмотрим CNF с оговорками

. Это удовлетворяется присваиванием

, но не

x

$x$

\neg x \lor y \lor \neg z

$\neg x\lor y\lor\neg z$

\neg y \lor z

$\neg y\lor z$

(1, 1, 1)

$(1,1,1)$

(0, 0, 0)

$(0,0,0)$

Эмиль Йержабек

Я думаю, что следующее определение

может работать. Пусть

- множество вершин

со свойством, которое для каждого

достижимого (направленным) путем из

достижимо путем из

. (Как модальный логик я бы описал это как объединение конечных кластеров транзитивного рефлексивного замыкания ориентированного графа, я не знаю, как бы это назвали теоретики графа.) Затем переверните все ребра с источником (отсюда и цель) в

Φ

$\Phi$

M

$M$

x

$x$

y

$y$

x

$x$

x

$x$

y

$y$

M

$M$

Эмиль Йержабек

@ Эмиль: Ах да, ты прав. Если я правильно понимаю ваше предложение, вы говорите, разбейте ориентацию на сильно связанные компоненты и переверните края внутри компонентов. Я думаю, что это работает. Я обновлю свой ответ соответственно. Большое спасибо!!

Эндрю Морган

Я не уверен, что моя идея понятна, поэтому я объясню на примере Джорджио:

. $( x_1 \lor x_2 \lor x_3 ) \land ( \lnot x_1 \lor \lnot x_3 \lor x_4 ) \land ( \lnot x_4 \lor x_5 ) \land ( \lnot x_2 \lor \lnot x_5 \lor \lnot x_6 )$

Сначала мне нужно изменить это в форме DNF:

. $( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

Это должно дать тот же ответ. И неважно, посчитал ли я число решений по модулю 2 для этого:

= 0 $( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

или для этого:

= 1. $( x_1 \land x_2 \land x_3 ) \lor ( \lnot x_1 \land \lnot x_3 \land x_4 ) \lor ( \lnot x_4 \land x_5 ) \lor ( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

Поэтому я выбираю второе. У меня есть участники:

= $i_0$ $( x_1 \land x_2 \land x_3 )$

= $i_1$ $( \lnot x_1 \land \lnot x_3 \land x_4 )$

= $i_2$ $( \lnot x_4 \land x_5 )$

= $i_3$ $( \lnot x_2 \land \lnot x_5 \land \lnot x_6 )$

Сейчас я строю систему уравнений:

${j_0}\oplus{j_1} = 1$

${j_0}\oplus{j_3} = 1$

${j_0}\oplus{j_1} = 1$

${j_2}\oplus{j_3} = 1$

${j_3} = 1$

Эта система имеет одно решение. 1 mod 2 = 1, поэтому ответ равен 1. Но встречается только один раз. Если каждая переменная встречается два раза, то возможно иметь ответ = 1? $x_6$

Маца
источник

Если мое мышление в порядке, то ответ «нет». Конечно, я предполагаю, что переменная встречается один раз в положительном и один раз в отрицании.

Мацей

Я забыл об уравнении для

= 1. Но результат, если то же самое. Одно из решений:

= 1,

= 0,

= 1,

= 0.

x_{4}

$x_4$

j_{1} \oplus j_{2}

${j_1}\oplus{j_2}$

j_{3}

$j_3$

j_{2}

$j_2$

j_{1}

$j_1$

j_{0}

$j_0$

Мацей

-1

извините за большую задержку. До сих пор, вероятно, проблема была решена. Если нет, я представлю свой полиномиальный алгоритм для решения . Сначала попробуем вычислить число решений по модулю 2 этого уравнения: . Где f и g - логические функции, а X - вектор переменных. Общая часть, , встречается два раза (один раз в f (X) и один раз в g (X)). Так что по модулю 2 общая часть не важна. Мы можем вычислить количество решений по модулю 2 из $\oplus\text{Rtw-Opp-CNF}$ ${f(X)}\oplus{g(X)}$ $f(X) \wedge g(X)$ $f(X)$ и число решений по модулю 2 из и затем суммируем эти результаты по модулю 2. Теперь давайте предположим, что функция представлена в следующем виде: $g(X)$

, $i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$

где является импликантом (я имею в виду переменные, связанные оператором AND; например: ). $i_j$ $x_0\wedge{x_1}\wedge{\neg{x_2}}$

Чтобы вычислить количество решений этой функции по модулю 2, мы можем просто вычислить число решений по каждому импликанту по модулю 2 и суммировать все результаты по модулю 2. Если у нас есть вектор переменных X и в импликанте нет всех переменных из этого вектора, то мы знаем это число решений по модулю 2 для этого импликанта равно 0, потому что есть решений, где k - количество отсутствующих переменных. Если импликант имеет все переменные, то число решений равно 1 (k = 0). Таким образом, вычисляется число решений по модулю 2 из легко. Теперь давайте рассмотрим: $2^k$ $i_0\oplus{i_1}\oplus{i_2}\oplus{...}\oplus{i_{n-1}}$

. $i_0\vee{i_1}\vee{i_2}\vee{...}\vee{i_{n-1}}$

Мы знаем, что . В общем случае операция OR может быть заменена на XOR каждого подмножества импликантов, связанных оператором AND. И это важный шаг: нас интересуют только те подмножества, которые: $a\vee{b} = a\oplus{b}\oplus({a\wedge{b}})$

1) имеет все переменные,

2) каждая переменная встречается точно одна (если переменная встречается два раза, то мы имеем положительное и отрицательное значение в одном импликанте, поэтому это будет равно 0).

$x_0$ $i_0$ $x_0$ $i_1$

${j_0}\oplus{j_1} = 1$

${j_0}$ ${j_1}$ $i_0$ $i_1$ $i_0$ $j_0$ $j_0$ $2^l$

Маца
источник

\oplus Rtw-Opp-CNF

$\oplus\text{Rtw-Opp-CNF}$

@AndrewMorgan Но формула с уникальным предложением, содержащим все переменные ровно один раз, не будет формулой с двойным чтением. Ограничение ровно в два раза, а не максимум в два раза.

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

x_{6}

$x_6$

(x_{1} \lor x_{2} \lor x_{3}) \land (\neg x_{1} \lor \neg x_{3} \lor x_{4}) \land (\neg x_{4} \lor x_{5}) \land (\neg x_{2} \lor \neg x_{5} \lor \neg x_{6})

$( x_1 \lor x_2 \lor x_3 ) \land ( \lnot x_1 \lor \lnot x_3 \lor x_4 ) \land ( \lnot x_4 \lor x_5 ) \land ( \lnot x_2 \lor \lnot x_5 \lor \lnot x_6 )$

x_{6}

$x_6$

(x_{1} \lor x_{2}) \land (\bar{x_{1}}) \land (\bar{x_{2}})

$(x_1 \vee x_2) \wedge (\bar{x_1}) \wedge (\bar{x_2})$

(x_{1} \lor x_{2}) \land (\bar{x_{1}} \lor \bar{x_{2}})

$(x_1 \vee x_2) \wedge (\bar{x_1} \vee \bar{x_2})$

(x_{1}) \land (\bar{x_{1}}) \land (x_{2}) \land (\bar{x_{2}})

$(x_1) \wedge (\overline{x_1}) \wedge (x_2) \wedge (\overline{x_2})$

@ AndrewMorgan Хорошо, теперь я вижу. Однако учтите, что и в семействе случаев, которое вы имели в виду, количество выполняемых заданий, похоже, остается четным. Вопрос, поставленный Мачей в его комментарии, оказывается сложным.

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