Формула 3-CNF, которая требует ширины разрешения

13

Напомним , что ширина резолюции опровержение R из формулы CNF F представляет максимальное число литералов в любом пункте , происходящих в R . Для каждого в 3-CNF wесть неудовлетворительные формулы F каждое опровержение разрешения F требует ширины не менее w .

Мне нужен конкретный пример неудовлетворительной формулы в 3-CNF (настолько малой и простой, насколько это возможно), у которой нет опровержения разрешения ширины 4.

Ян Йоханнсен
источник
Вам нужна ровно ширина 5 или хотя бы ширина 5? В последнем случае я думаю, что несколько случайных предложений на несколько переменных подойдут. Не очень красиво и не очень мало.
MassimoLauria
1
думаю, что относительно простой компьютерный / эмпирический поиск найдет это или исключит. также думаю, что здесь скрывается более общая / интересная неисследованная теория. см. также в доказательствах разрешения, все ли DAG возможны? , ищите вновь открытые голоса, если вы согласны =) связанный с этим вопрос: для формул -SAT, какие измерения (D) разрешают DAGs? m×n
vzn
Ян, я думаю, что Джейкоб должен быть в состоянии ответить на это легко. Кстати, вы хотели бы немного обобщить вопрос и спросить о методе, позволяющем придумать 3-CNF с данной шириной разрешения?
Каве
Массимо, мне нужен конкретный пример, который я могу записать и объяснить на доске или около того. Так что случайные предложения не подойдут.
Ян Йоханнсен
1
Сейчас я нахожусь не в том часовом поясе, чтобы мыслить правильно, но, может быть, подойдет формула Цейтина для некоторого действительно небольшого графика (где вы можете проверить расширение вручную)? Но вам действительно нужен 3-CNF? Для 4-CNF я, возможно, поигрался бы с прямоугольной сеткой подходящих размеров и посмотрел бы, что происходит. Просто очень недоделанные мысли ...
Якоб Нордстрем

Ответы:

14

Следующий пример взят из статьи, в которой Асериас и Далмау дают комбинаторную характеристику ширины разрешения ( журнал , ECCC , авторская копия ).

Теорема 2 статьи гласит, что при заданной формуле CNF опровержения разрешения ширины не более k для F эквивалентны выигрышным стратегиям для Спойлера в игре с экзистенциальной ( k + 1 ) -пебблью. Напомним , что экзистенциальный галька игра играется между двумя конкурирующими игроками, называемых Спойлер и Дубликатор и позиции игры частичные задания размера домена в большинстве к + 1 к переменным F . В игре ( k + 1 ) -pebble, начиная с пустого задания, Спойлер хочет фальсифицировать предложение из FFkF(k+1)k+1F(k+1)Fзапоминая не более логических значений за раз, и Duplicator хочет помешать Спойлеру сделать это.k+1

Пример основан на (отрицании) принципа голубиных отверстий.

Для каждого и j { 1 , , n } пусть p i , j - пропозициональная переменная, означающая, что голубь i сидит в отверстии j . Для каждого i { 1 , , n + 1 } и j { 0 , , n } пустьi{1,,n+1}j{1,,n}pi,jiji{1,,n+1}j{0,,n}yi,j3EPii

EPi¬yi,0j=1n(yi,j1pi,j¬yi,j)yi,n.
3EPHPnn+1EPiHki,j¬pi,k¬pj,ki,j{1,,n+1},ijk{1,,n}

nEPHPnn+1, hence EPHPnn+1 has no resolution refutation of width at most n1.

The paper has another example in Lemma 9, based on the dense linear order principle.

Given that computing the minimum width for resolution refutations is EXPTIME-complete, and moreover it takes Ω(n(k3)/12) time to certify that the minimum width is at least k+1 (see Berkholz's paper in FOCS or arXiv), perhaps it is hard to come up with examples which provably need wide resolution refutations?

siuman
источник
2
OK I should have known that. So EPHP56 (slightly simplified) would be an example that has 48 variables and about 100 clauses. If nothing significantly simpler comes up, I will accept this answer.
Jan Johannsen