Укороченная версия.
Первоначальное доказательство того, что # 2-SAT является #P -завершенным, фактически показывает, что экземпляры # 2-SAT являются монотонными (без учета отрицаний каких-либо переменных) и двудольными (график, образованный предложениями над Переменный является двудольным графом) являются #P -Жесткими. Таким образом, два случая # 2-ТОН-SAT и № 2-двудольный-SAT является #P -Жестким. Существуют ли другие специальные случаи , которые могут быть охарактеризованы с точки зрения «естественных» свойств формулы, которые также #P -Жесткий?
Длинная версия.
Проблема # 2-SAT - это задача вычисления - для булевой формулы состоящей из соединения нескольких предложений, где каждое предложение - это дизъюнкция двух литералов или - количество логических строк такое, что . Узнать, существует ли такой или нет, легко; но подсчет числа решений в целом является # P- полным, как показал Валиант в книге «Сложность подсчета и проблемы надежности», SIAM J. Comput., 8 , с. 410–421 .
В частности, для случая # 2-SAT, что фактически показывает Valiant, это сокращение до # 2-SAT от подсчета совпадений (в том числе несовершенных) в двудольных графах, что приводит к появлению # 2-SAT с очень специфической структурой , следующее.
Во-первых, обратите внимание, что монотонная задача эквивалентна по замещению проблеме, в которой для каждой переменной либо встречается в формуле либо , но не то и другое одновременно. В частности, проблема «монотонного убывания», в которой для каждой переменной встречаются только отрицания является такой же сложной, как и монотонный случай.
Для любого графа с ребрами мы можем построить монотонно убывающую формулу 2-SAT, соответствующую сопоставлениям - ребер, которые не имеют общих вершин, - назначив переменную каждому ребру, представляющую, он включен в набор ребер; свойство множества являющегося совпадающим, эквивалентно вектору инцидентности удовлетворяющему формуле CNF ϕ , условия которой задаются как ( ˉ x e ∨ ˉ x f ) для каждой пары ребер e , f ∈ Eкоторые разделяют вершину. По построению, имеет столько удовлетворяющих решений х ∈ { 0 , 1 } м , как есть (возможно , несовершенно) паросочетания в графе G .
Если граф для которого мы хотим посчитать совпадения, является двудольным, то он не содержит нечетных циклов - которые мы можем описать как последовательность ребер в графе, который начинается и заканчивается одним и тем же ребром (без учета этого последнего ребра дважды) , Тогда в ϕ нет последовательности переменных x e , x f , x g , … , x e нечетной длины , в которых смежные переменные входят в общее предложение. Тогда формула ϕ будет двудольной, как описано ранее.
B G G k G n { 0 , 1 }подсчитав их, можно определить количество соответствий в размера (то есть, которые являются идеальными совпадениями); и обратите внимание, что подсчет числа совершенных совпадений в двудольных графах эквивалентен вычислению перманентов -матриц простым соответствием.
Класс экземпляров # 2-SAT, которые показаны как #P -hard, являются монотонными двудольными экземплярами.
Вопрос: Каковы другие особые случаи # 2-SAT, которые # P- завершены, в результате этого или некоторого другого сокращения?
Было бы интересно, если бы, помимо показа / цитирования сокращения, люди могли также описать интуитивную причину того, как особый случай может создавать препятствия для естественных подходов к подсчету сатисификационных заданий. Например, хотя MONOTONE-2-SAT тривиально разрешимо ( - всегда решение), монотонные экземпляры - это те, в которых назначение некоторой переменной фиксированному значению обычно не налагает много ограничений на остальные переменные. Исправление любой переменной x j = 0 ограничивает только значения переменных, непосредственно связанных с ней некоторым предложением; и установка x j = 1не ограничивает возможные значения любых других переменных вообще. (Однако не ясно, что сопоставимое ограничение для двудольных графов имеет существенное значение, однако; двудольное ограничение скорее добавляет структуру, чем удаляет ее, но не может добавить структуру, достаточную для эффективного подсчета.)
Отредактировано, чтобы добавить. Бонусные баллы будут начисляться за любой такой класс, который в конечном итоге не зависит от существования монотонных экземпляров (как это делается выше # 2-BIPARTITE-SAT, чья жесткость, по- видимому, обусловлена включением особого случая #P -hard # 2). -MONOTONE-двудольный-сБ). Например, аргумент в пользу твердости # 2-BIPARTITE-SAT, который не опирается на монотонные экземпляры (но может опираться на некоторые другие подсемейства), был бы интересен.
источник
Ответы:
# 3-Регулярная двудольная плоская вершинная оболочка # P-Complete
Поскольку подсчет покрытий вершин точно такой же, как подсчет удовлетворяющих назначений монотонного экземпляра # 2-SAT, приведенный выше результат подразумевает, что он # P-завершен для подсчета удовлетворяющих назначений экземпляра # 2-SAT, который является монотонным и 3-регулярным и двудольный и плоский .
Это, в свою очередь, означает, что в дополнение к двум специальным случаям # 2-MONOTONE-SAT и # 2-BIPARTITE-SAT, уже упомянутым в этом вопросе, два специальных случая # 2-CUBIC-SAT и # 2-PLANAR-SAT # P-полный, а также.
источник