Формула Restricted Monotone 3CNF: подсчет удовлетворяющих заданий (оба по модулю

9

Рассмотрим формулу Monotone 3CNF, имеющую оба следующих дополнительных ограничения:

  • Каждая переменная появляется в точности 2 статьи.
  • Учитывая любой 2 пункты, они разделяют не более 1 переменная.

Я хотел бы знать, насколько сложно рассчитывать удовлетворяющие задания такой формулы.


Обновление 04.06.2013 12:55

Хотелось бы также узнать, насколько сложно определить соотношение числа удовлетворяющих заданий.


Обновление 04.11.2013 22:40

Что если в дополнение к описанным выше ограничениям мы также введем оба следующих ограничения:

  • Формула плоская.
  • Формула двудольная.

Обновление 16/04/2013 23:00

Каждое удовлетворяющее задание соответствует краевому покрытию 3регулярный граф. После тщательного поиска единственная релевантная статья, которую мне удалось найти по счетным краям, - это (3-я), уже упомянутая в ответе Ювала. В начале такой бумаги, авторы говорят «Мы инициируем изучение выборки (и связанный с ним вопрос о подсчете) всех краевых покрытий графа» . Я очень удивлен, что этой проблеме уделяется так мало внимания (по сравнению со счетом покрытий вершин, который широко изучен и гораздо лучше понят для нескольких классов графов). Мы не знаем, является ли подсчет краевых покрытий#п-жесткий. Мы не знаем, является ли определение четности числа краевых покрытийпТяжело, либо.


Обновление 06.09.2013 07:38

Определение четности количества краевых покрытий п-Твердо, проверьте ответ ниже.

Джорджио Камерани
источник
Я думаю, что это более интересно, если вы ограничите его литералами вместо переменных.
Тайфун Pay
3
@Tayfun Так как формула является монотонной, они эквивалентны.
Тайсон Уильямс
@TysonWilliams Спасибо, я не должен комментировать вещи, когда я сонный.
Тайфун платят
2
@ Джорджио Используя существующие сокращения, может быть нетрудно доказать, что проблема #п-жесткий. Вы должны попробовать прочитать соответствующие части двух других работ, которые я цитирую.
Yuval Filmus
@Downvoter: почему?
Джорджио Камерани

Ответы:

6

В любом графе четность числа покрытий вершин равна четности числа покрытий ребер.

Чтобы понять почему, проверьте этот ответ и понаблюдайте, как|С| равен паритету Δ|В|знак равноО|В|-Е|В|что в свою очередь равно паритету О|В|+Е|В|, который является числом краевых покрытий.

Вычисление четности числа покрытий вершин P-hard: поэтому вычисление четности числа ребер покрытия П-хард тоже.

По крайней мере, вторая половина вопроса была решена.

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

Ваша проблема, вероятно, # P-полная, хотя я не смог найти ее в литературе.

Еще один способ сформулировать вашу проблему - «# 3-normal-edge-cover». По заданной формуле создайте граф, в котором каждое предложение соответствует вершине, а каждая переменная соответствует ребру. Поскольку формула является 3CNF, график является 3-регулярным (или имеет максимальную степень 3, в зависимости от определения). Кроме того, график прост. Удовлетворительное задание такое же, как у края обложки.

Вот несколько связанных проблем:

Юваль Фильмус
источник
1
Я не понимаю, как его # disabled-Monotone3CNF - это то же самое, что и # 1-Ex3MonoSAT. Не говоря уже о том, что более поздняя проблема хочет, чтобы был удовлетворен ровно один литерал. Он хочет, чтобы формулы CNT Monotone 3 были такими, чтобы каждая переменная фигурировала ровно в двух предложениях, а в каждом предложении не более 1 переменной. В # 1-Ex3MonoSAT такого ограничения нет.
Тайфун платят
2
Я пытался передать это различие, используя слово «только», но я согласен, что это не самый лучший выбор слов.
Юваль Фильмус