Каковы # P-полные подсемейства # 2-SAT?

17

Укороченная версия.

Первоначальное доказательство того, что # 2-SAT является #P -завершенным, фактически показывает, что экземпляры # 2-SAT являются монотонными (без учета отрицаний каких-либо переменных) и двудольными (график, образованный предложениями над Переменный является двудольным графом) являются #P -Жесткими. Таким образом, два случая # 2-ТОН-SAT и № 2-двудольный-SAT является #P -Жестким. Существуют ли другие специальные случаи , которые могут быть охарактеризованы с точки зрения «естественных» свойств формулы, которые также #P -Жесткий?

Длинная версия.

Проблема # 2-SAT - это задача вычисления - для булевой формулы состоящей из соединения нескольких предложений, где каждое предложение - это дизъюнкция двух литералов или - количество логических строк такое, что . Узнать, существует ли такой или нет, легко; но подсчет числа решений в целом является # P- полным, как показал Валиант в книге «Сложность подсчета и проблемы надежности», SIAM J. Comput., 8 , с. 410–421 .φИксJИкс¯JИкс{0,1}Nφ(Икс)знак равно1Икс

В частности, для случая # 2-SAT, что фактически показывает Valiant, это сокращение до # 2-SAT от подсчета совпадений (в том числе несовершенных) в двудольных графах, что приводит к появлению # 2-SAT с очень специфической структурой , следующее.

  1. Во-первых, обратите внимание, что монотонная задача эквивалентна по замещению проблеме, в которой для каждой переменной либо встречается в формуле либо , но не то и другое одновременно. В частности, проблема «монотонного убывания», в которой для каждой переменной встречаются только отрицания является такой же сложной, как и монотонный случай.ИксJИксJφИкс¯JИкс¯J

  2. Для любого графа с ребрами мы можем построить монотонно убывающую формулу 2-SAT, соответствующую сопоставлениям - ребер, которые не имеют общих вершин, - назначив переменную каждому ребру, представляющую, он включен в набор ребер; свойство множества являющегося совпадающим, эквивалентно вектору инцидентности удовлетворяющему формуле CNF ϕ , условия которой задаются как ( ˉ x eˉ x f ) для каждой пары ребер e , f Eграммзнак равно(В,Е)мxeMEx=χMϕ(x¯ex¯f)e,fEкоторые разделяют вершину. По построению, имеет столько удовлетворяющих решений х{ 0 , 1 } м , как есть (возможно , несовершенно) паросочетания в графе G .ϕx{0,1}mG

  3. Если граф для которого мы хотим посчитать совпадения, является двудольным, то он не содержит нечетных циклов - которые мы можем описать как последовательность ребер в графе, который начинается и заканчивается одним и тем же ребром (без учета этого последнего ребра дважды) , Тогда в ϕ нет последовательности переменных x e , x f , x g , , x e нечетной длины , в которых смежные переменные входят в общее предложение. Тогда формула ϕ будет двудольной, как описано ранее.Gxe,xf,xg,,xeϕϕ

  4. G=(AB,E)A,BnGkAB G G k G n { 0 , 1 }0knBGGkподсчитав их, можно определить количество соответствий в размера (то есть, которые являются идеальными совпадениями); и обратите внимание, что подсчет числа совершенных совпадений в двудольных графах эквивалентен вычислению перманентов -матриц простым соответствием.Gn{0,1}

Класс экземпляров # 2-SAT, которые показаны как #P -hard, являются монотонными двудольными экземплярами.

Вопрос: Каковы другие особые случаи # 2-SAT, которые # P- завершены, в результате этого или некоторого другого сокращения?

Было бы интересно, если бы, помимо показа / цитирования сокращения, люди могли также описать интуитивную причину того, как особый случай может создавать препятствия для естественных подходов к подсчету сатисификационных заданий. Например, хотя MONOTONE-2-SAT тривиально разрешимо ( - всегда решение), монотонные экземпляры - это те, в которых назначение некоторой переменной фиксированному значению обычно не налагает много ограничений на остальные переменные. Исправление любой переменной x j = 0 ограничивает только значения переменных, непосредственно связанных с ней некоторым предложением; и установка x j = 1x=1nxj=0xj=1не ограничивает возможные значения любых других переменных вообще. (Однако не ясно, что сопоставимое ограничение для двудольных графов имеет существенное значение, однако; двудольное ограничение скорее добавляет структуру, чем удаляет ее, но не может добавить структуру, достаточную для эффективного подсчета.)

Отредактировано, чтобы добавить. Бонусные баллы будут начисляться за любой такой класс, который в конечном итоге не зависит от существования монотонных экземпляров (как это делается выше # 2-BIPARTITE-SAT, чья жесткость, по- видимому, обусловлена ​​включением особого случая #P -hard # 2). -MONOTONE-двудольный-сБ). Например, аргумент в пользу твердости # 2-BIPARTITE-SAT, который не опирается на монотонные экземпляры (но может опираться на некоторые другие подсемейства), был бы интересен.

Ниль де Бодрап
источник
Не совсем то, что вы просили в конце вашего вопроса, но есть сокращение, которое при произвольной формуле CNF возвращает формулу 2-SAT Ψ, которая не является монотонной и которая имеет следующее свойство: число решений Ψ имея нечетное число переменных, равное true, за вычетом количества решений Ψ, имеющее четное число переменных, равное true, равно числу решений Φ . ΦΨΨΨΦ
Джорджио Камерани
Я забыл сказать , что также двудольная. Ψ
Джорджио Камерани

Ответы:

15

# 3-Регулярная двудольная плоская вершинная оболочка # P-Complete

Поскольку подсчет покрытий вершин точно такой же, как подсчет удовлетворяющих назначений монотонного экземпляра # 2-SAT, приведенный выше результат подразумевает, что он # P-завершен для подсчета удовлетворяющих назначений экземпляра # 2-SAT, который является монотонным и 3-регулярным и двудольный и плоский .

Это, в свою очередь, означает, что в дополнение к двум специальным случаям # 2-MONOTONE-SAT и # 2-BIPARTITE-SAT, уже упомянутым в этом вопросе, два специальных случая # 2-CUBIC-SAT и # 2-PLANAR-SAT # P-полный, а также.

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