Подсчет растворов формул Монотон-2CNF

13

Формула Monotone-2CNF - это формула CNF, в которой каждое предложение состоит ровно из двух положительных литералов.

Теперь у меня есть Монотонный-2CNF формула . Пусть S будет множеством удовлетворяющих заданий F. У меня также есть оракул O, который может дать следующую информацию:FSFO

  1. Мощность множества (т. Е. Количество решений F ).SF
  2. Учитывая переменную : x
    • Число решений в содержащих положительный литерал x .Sx
    • Число решений в содержащих отрицательный литерал ¬ x .S¬x
  3. Дано 2 переменные и х 2 : x1x2
    • Количество решений в содержащих x 1x 2 .Sx1x2
    • Количество решений в содержащих x 1¬ x 2 .Sx1¬x2
    • Количество решений в содержащих ¬ x 1x 2 .S¬x1x2
    • Число растворов в содержащих ¬ x 1¬ x 2 .S¬x1¬x2

Обратите внимание , что оракул будет «ограничена»: он работает только на F , он не может быть использован по формуле F 'F .OFFF


Вопрос:

С учетом 3 переменных , х 2 , х 3 является возможным определить количество решений в S , содержащих ¬ х 1¬ х 2¬ х 3 в полиномиальное время, используя F и информацию , предоставленную O ?x1x2x3S¬x1¬x2¬x3FO

Замечания:

Вы можете заменить в вопросе с тем, что еще из 8 возможных комбинаций х 1 , х 2 , х 3 . Проблема останется прежней.¬x1¬x2¬x3x1x2x3


Эмпирический факт:

Я столкнулся со следующим эмпирическим фактом неделю назад. Пусть будет множеством этих решений, содержащих ¬ x 1¬ x 2 , и пусть S ¬ x 1¬ x 2x 3S будет множеством тех решений, содержащих ¬ x 1¬ х 2х 3 . Теперь, похоже, дело в том, что если условие CS¬x1¬x2S¬x1¬x2S¬x1¬x2x3S¬x1¬x2x3C имеет место, это соотношение также выполняется:

гдеϕ=1.618033 ...золотое сечение. УсловиеCвыглядит следующим образом:«x1,x2,x3упоминаются вFпочти одинаковое количество раз».|S¬x1¬x2||S¬x1¬x2x3|ϕ

ϕ=1.618033...Cx1x2x3F

Джорджио Камерани
источник
1
Когда вы говорите «решения, содержащие отрицательный литерал -x», вы имеете в виду «решения с x = 0»?
Noam
@Noam: Да, именно так.
Джорджио Камерани
1
Простое наблюдение: поскольку число возможных вопросов к оракулу O ограничено полиномиально, без потери общности вы можете задать все вопросы в начале алгоритма. Поэтому мы можем заменить оракула дополнительным вводом, обещая, что эти цифры верны. Я думаю, что эта формулировка обещания немного проще, чем рассматривать ее как оракула.
Цуёси Ито
@ Tsuyoshi: Да, я согласен с вами.
Джорджио Камерани,
1
@vzn: Версия решение 2CNF в . Это счетная версия монотонного случая (учитывая монотонную формулу F 2CNF , вы должны вычислить, сколько у нее удовлетворительных назначений). PF
Джорджио Камерани

Ответы:

5

Чтобы использовать этот эмпирический факт, вы действительно хотите знать, могут ли приблизительные числа давать другим приблизительные числа. Но для точного случая, я думаю, может быть прямой способ показать, что это сложно. Вот эскиз.

Сначала отметим, что удовлетворяющие назначения соответствуют независимым множествам в графе. Я буду использовать фразу «S-проекцию I (G)» , чтобы описать отображение функции к числу независимых множеств I с I П S = T . «K-проекции» - это S-проекции для всех подмножеств S из V с | S | = к .TSIS=T|S|=k

Схема доказательства:

  1. Если 2-проекции дают 3-проекции, они также дают k-проекции в политиме для каждого k.
  2. Если 2-проекции дают 4-проекции, то число независимых множеств графа указывается в FP, поэтому FP = # P.

(1) Пусть такое, что (k-1) -проекции дают k-проекции. Учитывая график, его K-проекции, а х 1 , . , , , Х к , v G , мы будем вычислять проекции на х 1 , . , , , х к , v .k3x1,...,xk,vGx1,...,xk,v

Define the graph G by attaching a fresh vertex to v. This can be seen as weighting v. The (k-1)-projections of G can be computed because we know the k-projections of G. So then we have the k-projections of G. And this gives x1,...,xk,v-projections of G.

e1,...,emGke1,...,ekGk+1GkG02|G|

Colin McQuillan
источник
I would prefer not to use that empirical fact! I prefer the exact count of course. But incidentally I noticed that fact while trying to determine the exact count.
Giorgio Camerani
Thanks for your answer. Yes, it's hard: as you say, a positive answer to this question would imply #P = FP.
Giorgio Camerani
7

Some observations, not an answer.

Further to the note to the question, any combination of 3 literals can be expressed in terms of any other combination of literals on the same variables, together with a small number of terms that the oracle can provide. This follows from looking at the Venn diagram of 3 intersecting sets, and expressing each of the 8 regions in terms of the other regions. Note that this does not require the formula to be either monotone or 2CNF.

It is also clear that the number of solutions satisfying any 3-literal conjunct can be expressed as the sum of 2n3 terms, each of which is either 0 or 1, expressing a particular assignment to all variables. Each of these can be evaluated in linear time, but there are exponentially many terms to evaluate, so this doesn't satisfy the requirements.

Hence the question is really about whether it is possible to exploit the property of being monotone 2CNF to compress this exponential-size expression to polynomial size.

I tried to look at a simpler question, restricting the oracle to just an advice string with the number of solutions, when the counts for single or pairwise literal combinations are not available. I cannot see any way to exploit knowledge of the number of solutions to obtain a quick calculation of the number of solutions with respect to any single literal.

Is there something about monotone 2CNF that would allow the number of solutions in S containing x1 to be obtained quickly, if one knew |S|?

András Salamon
источник
2
Indeed, the given information needs to be powerful enough to defeat the underlying hardness. It is known that there is no fpras for solutions to monotone 2-SAT unless NP = RP.
mhum
@Andras: What here is called "oracle" is just some sort of dictionary D. It seems the case that such dictionary D can be constructed incrementally, by updating it each time a new clause is added to F. The problem is that, in order to correctly update D, I have to answer this question.
Giorgio Camerani
@Walter: Yes, I understand that. My point is that even a much simpler case is not clear: going from the total number of solutions to the number of solutions containing a single literal.
András Salamon
1
It could be that your formula is essentially linear: independent sets in a path follow the Fibonacci sequence. One way to see this is that the partition function (1 1; 1 0) has phi as an eigenvalue.
Colin McQuillan
3
I happened to find some slides discussing a more rigorous result: isid.ac.in/~antar/Talks/Counting-Hard-Core_KBS_slides.pdf (see page 11)
Colin McQuillan