Минимальные неудовлетворительные формулы 3-CNF

В настоящее время я заинтересован в получении (или построении) и изучении формул 3-CNF, которые являются неудовлетворительными и имеют минимальный размер. То есть они должны состоять из как можно меньшего числа предложений (предпочтительно m = 8) и как можно меньшего числа различных переменных (n = 4 или более), чтобы удаление хотя бы одного предложения сделало формулу выполнимой.

Более формально, любая квалифицирующая 3-CNF формула F должна удовлетворять следующим условиям:

F неудовлетворителен
F имеет минимальное количество (4+) различных переменных (или их отрицание)
F имеет минимальное количество пунктов (8+)
каждое собственное подмножество F является выполнимым (что позволяет удалить любое произвольное предложение или пункты).
В F нет двух предложений, которые сводятся к предложению 2-CNF, например (i, j, k) & (i, j, ~k), НЕ допускаются (они сокращаются до (i,j))

Например, при n = 4 существует много минимальных 8-пунктовых 3-CNF-формул, которые являются неудовлетворительными. Например, взглянув на 4-гиперкуб и попытавшись накрыть его ребрами (2-гранями), можно построить следующую неудовлетворительную формулу:

1. (~A,  B,  D)
2. (~B,  C,  D)
3. ( A, ~C   D)
4. ( A, ~B, ~D)
5. ( B, ~C, ~D)
6. (~A,  C, ~D)
7. ( A,  B,  C)
8. (~A, ~B, ~C)

Это квалифицируется как минимальная неудовлетворительная формула 3-CNF, потому что:

Это неудовлетворительно
- Пункты 1-3 эквивалентны: D or A=B=C
- Пункты 4-6 эквивалентны: ~D or A=B=C
- Они подразумевают A=B=C, но согласно пунктам 7 и 8 это противоречие.
Есть только 4 различных переменных.
Всего 8 пунктов.
Удаление любого пункта делает его удовлетворительным.
Никакие 2 предложения не сводятся к предложению 2-CNF.

Итак, я думаю, что мои общие вопросы приведены в порядке важности для меня:

Каковы некоторые другие маленькие минимальные формулы, которые удовлетворяют вышеуказанным условиям? (например, 4,5,6 переменных и 8,9,10 предложений)
Есть ли какая-то база данных или «атлас» таких минимальных формул?
Какие неслучайные алгоритмы существуют для их прямого построения, если таковые имеются?
Каковы некоторые характеристики этих формул? Могут ли они быть подсчитаны или оценены с учетом n (# переменных) и m (# предложений)?

Заранее благодарю за ваши ответы. Я приветствую любой ответ или комментарий.

cc.complexity-theory sat MAF
источник

Каждое предложение 3-CNF не допускает 1/8 возможных решений. Очевидно, что вам всегда нужно по крайней мере 8 предложений или больше, если наборы запрещенных решений перекрываются. Поскольку ваше условие 5 запрещает неперекрывающиеся наборы запрещенных решений для n = 3, вам нужно более 8 предложений для этого случая: обратите внимание, что ваш пример не подчиняется условию 5.

Андрас Саламон

Да, вы правы по всем пунктам Андраш. 8 пунктов являются обязательным минимумом для неудовлетворительной формулы 3-CNF, и поэтому условие 5 может быть слишком ограничительным для моих целей при поиске / построении квалификационных формул. Я понимаю, что при n = 3 условие 5 обязательно должно быть нарушено, но оно было включено только в иллюстративных целях. Я строго заинтересован в квалификационных формулах размером n = 4 + (т.е. 4 или более переменных, но не слишком много больше.). Возможно, я поцарапаю условие 5.

MAF

Я думаю, что ваш «пример» с n = 3 скорее сбивающий с толку, чем иллюстративный, потому что (как отметил Андраш в своем комментарии) на самом деле это не пример того, о чем вы спрашиваете в этом вопросе. Пример с n = 4 прекрасно и наглядно. Почему бы вам просто не удалить пример с n = 3?

Цуёси Ито

Хороший вопрос, Цуеши. Выполнено.

МАФ

@MAF: удаление условия 5 приводит к тривиальному примеру: начните с неудовлетворительного экземпляра, содержащего предложения и , затем замените каждое предложение двумя предложениями и для новой переменной и продолжайте, пока все предложения не будут иметь 3 литерала. Это дает 7 переменных неудовлетворительной формулы с 8 предложениями. Это просто разбивает пространство решения на 8 непересекающихся частей, что обычно не является интересным кодом.

{x}

$\{x\}$

{x^{'}}

$\{x'\}$

C

$C$

C \cup {v}

$C \cup \{v\}$

C \cup {v^{'}}

$C \cup \{v'\}$

v

$v$

Андрас Саламон

Ответы:

Возьмите формулу в вашем примере, удалите предложение и добавьте следующие предложения: $\lnot A \lor \lnot B \lor \lnot C$ $2$

$\lnot A \lor \lnot B \lor \lnot E$
$\lnot B \lor \lnot C \lor E$

Вы получите минимальную неудовлетворительную формулу с , соблюдая условие 5. $n=5$ $m=9$

В общем, вы можете случайным образом выбрать пункт и разделить его на предложения: $l_1 \lor l_2 \lor l_3$ $2$

$l_1 \lor l_2 \lor v$
$l_2 \lor l_3 \lor \lnot v$

где это новая переменная. Каждый раз, когда вы делаете это, оба и увеличиваются на . Повторение этого процесса позволяет вам «растянуть» исходное неудовлетворенное ядро и получить минимальные неудовлетворительные формулы (соблюдая условие 5), у которых стремится к при (что довольно редко, как формулы с выполнимо с большой вероятностью). $v$ $n$ $m$ $1$ $r=\frac{m}{n}$ $1$ $n$ $r=1$

Джорджо Камерани
источник

Спасибо за ответ, Уолтер. Процедура, которую вы описываете, действительно очень полезна для генерации еще чуть более крупных формул min unsat «похожей» структуры, то есть, если у вас есть базовый набор, который, по вашему мнению, имеет интересные свойства.

МАФ

@ MAF: Добро пожаловать. Спасибо за размещение такого интересного вопроса.

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

Я считаю, что условие № 5 на самом деле не выполняется в вашем примере и не может быть выполнено никогда.
Пусть следующие пункты эквивалентны:

( p, q) = (~A,B,D)(A,~B,~D)

Что позволит нам отобразить предложения A, B, C и D на новые переменные p, q, r и s в виде следующей таблицы истинности:

A B C D | p q r s
-----------------
0 0 0 0 | 0 1 0 0
0 0 0 1 | 0 1 0 1
0 0 1 0 | 0 1 1 0
0 0 1 1 | 0 1 1 1
-----------------
0 1 0 0 | 1 0 0 0
0 1 0 1 | 0 0 0 0
0 1 1 0 | 1 0 0 1
0 1 1 1 | 0 0 0 1
-----------------
1 0 0 0 | 0 0 1 0
1 0 0 1 | 1 0 1 0
1 0 1 0 | 0 0 1 1
1 0 1 1 | 1 0 1 1
-----------------
1 1 0 0 | 1 1 0 0
1 1 0 1 | 1 1 0 1
1 1 1 0 | 1 1 1 0
1 1 1 1 | 1 1 1 1
-----------------

И теперь мы можем выразить предложения A, B, C и D через p, q, r и s:

1. (~A,  B,  D) = ( p, q,~r, s)( p, q,~r,~s)
2. (~B,  C,  D) = (~p, q, r, s)(~p,~q, r, s)
3. ( A, ~C   D) = ( p,~q,~r, s)(~p, q, r,~s)
4. ( A, ~B, ~D) = ( p, q, r, s)( p, q, r,~s)
5. ( B, ~C, ~D) = ( p,~q,~r,~s)(~p, q,~r,~s)
6. (~A,  C, ~D) = (~p, q,~r, s)(~p,~q, r,~s)
7. ( A,  B,  C) = ( p,~q, r, s)( p,~q, r,~s)
8. (~A, ~B, ~C) = (~p,~q,~r, s)(~p,~q,~r,~s)

Поскольку все пункты показаны и связаны с предложениями A, B, C и D. Тогда мы можем утверждать, что предложения p, q, r и s можно сократить до:

( p, q, r)
( p, q,~r)
( p,~q, r)
( p,~q,~r)
(~p, q, r)
(~p, q,~r)
(~p,~q, r)
(~p,~q,~r)

Что, очевидно, нарушает условие № 5.

Я хочу отметить, что даже в примере явно не показано, что есть 2 предложения, которые могут быть сокращены до 2-CNF, но неявно это имеет (например, (~ A, B, D) и (A, ~ B, ~ D)), вы, возможно, не сможете выразить 2-CNF с заданными переменными, но когда вы введете другое отображение для проблемы, вы сможете выразить их.

Хазам Алхамдан
источник