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

19

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

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

  1. F неудовлетворителен
  2. F имеет минимальное количество (4+) различных переменных (или их отрицание)
  3. F имеет минимальное количество пунктов (8+)
  4. каждое собственное подмножество F является выполнимым (что позволяет удалить любое произвольное предложение или пункты).
  5. В 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. Это неудовлетворительно

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

  3. Всего 8 пунктов.
  4. Удаление любого пункта делает его удовлетворительным.
  5. Никакие 2 предложения не сводятся к предложению 2-CNF.

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

  1. Каковы некоторые другие маленькие минимальные формулы, которые удовлетворяют вышеуказанным условиям? (например, 4,5,6 переменных и 8,9,10 предложений)

  2. Есть ли какая-то база данных или «атлас» таких минимальных формул?

  3. Какие неслучайные алгоритмы существуют для их прямого построения, если таковые имеются?

  4. Каковы некоторые характеристики этих формул? Могут ли они быть подсчитаны или оценены с учетом n (# переменных) и m (# предложений)?

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

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?
Цуёси Ито
Хороший вопрос, Цуеши. Выполнено.
МАФ
1
@MAF: удаление условия 5 приводит к тривиальному примеру: начните с неудовлетворительного экземпляра, содержащего предложения и , затем замените каждое предложение двумя предложениями и для новой переменной и продолжайте, пока все предложения не будут иметь 3 литерала. Это дает 7 переменных неудовлетворительной формулы с 8 предложениями. Это просто разбивает пространство решения на 8 непересекающихся частей, что обычно не является интересным кодом. {x}{x}CC{v}C{v}v
Андрас Саламон

Ответы:

11

Возьмите формулу в вашем примере, удалите предложение и добавьте следующие предложения: ¬A¬B¬C2

¬A¬B¬E
¬B¬CE

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

В общем, вы можете случайным образом выбрать пункт и разделить его на предложения: l1l2l32

л 2л 3¬ vl1l2v
l2l3¬v

где это новая переменная. Каждый раз, когда вы делаете это, оба и увеличиваются на . Повторение этого процесса позволяет вам «растянуть» исходное неудовлетворенное ядро ​​и получить минимальные неудовлетворительные формулы (соблюдая условие 5), у которых стремится к при (что довольно редко, как формулы с выполнимо с большой вероятностью).н м 1 р = мvnm1 1nr=1r=mn1nr=1

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

Я считаю, что условие № 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 с заданными переменными, но когда вы введете другое отображение для проблемы, вы сможете выразить их.

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