Zliczanie roztworów wzorów Monotone-2CNF

Formuła Monotone-2CNF to formuła CNF, w której każda klauzula składa się z dokładnie 2 literałów dodatnich.

Teraz mam wzór Monotone-2CNF . Niech S będzie zbiorem satysfakcjonujących zadań F. Mam również wyrocznię O, która może podać następujące informacje:$F$$S$$F$$O$

1. Kardynalność zbioru (tj. Liczba rozwiązań F ).$S$$F$
2. Biorąc pod uwagę zmienną : $x$
   • Liczba rozwiązań w zawierających literał dodatni x .$S$$x$
   • Liczba rozwiązań w zawierających literał ujemny ¬ x .$S$$\lnot x$
3. Biorąc pod uwagę 2 zmienne i x 2 : $x_1$$x_2$
   • Liczba rozwiązań w zawierających x 1 ∧ x 2 .$S$$x_1 \land x_2$
   • Liczba rozwiązań w zawierających x 1 ∧ ¬ x 2 .$S$$x_1 \land \lnot x_2$
   • Liczba rozwiązań w zawierających ¬ x 1 ∧ x 2 .$S$$\lnot x_1 \land x_2$
   • Liczba rozwiązań w zawierających ¬ x 1 ∧ ¬ x 2 .$S$$\lnot x_1 \land \lnot x_2$

Należy zauważyć, że Oracle jest „ograniczony”: to działa tylko na F , to nie może być stosowany na formule F ' ≠ F .$O$$F$$F' \neq F$

Pytanie:

Biorąc pod uwagę 3 zmienne , x 2 , x 3, czy można określić liczbę rozwiązań w S zawierających ¬ x 1 ∧ ¬ x 2 ∧ ¬ x 3 w czasie wielomianowym, używając F i informacji dostarczonych przez O ?$x_1$$x_2$$x_3$$S$$\lnot x_1 \land \lnot x_2 \land \lnot x_3$$F$$O$

Uwaga:

Możesz zastąpić w pytaniu dowolną inną z 8 możliwych kombinacji x 1 , x 2 , x 3 . Problem pozostałby taki sam.$\lnot x_1 \land \lnot x_2 \land \lnot x_3$$x_1$$x_2$$x_3$

Fakt empiryczny:

Tydzień temu natknąłem się na następujący fakt empiryczny. Niech będzie zbiorem roztworów zawierających ¬ x 1 ∧ ¬ x 2 , a S ¬ x 1 ∧ ¬ x 2 ∧ x 3 ⊂ S będzie zbiorem tych roztworów zawierających ¬ x 1 ∧ ¬ x 2 ∧ x 3 . Wydaje się, że tak jest, jeśli warunek $S_{\lnot x_1 \land \lnot x_2} \subset S$$\lnot x_1 \land \lnot x_2$$S_{\lnot x_1 \land \lnot x_2 \land x_3} \subset S$$\lnot x_1 \land \lnot x_2 \land x_3$$C$trzyma, ta relacja obejmuje również:

gdzieϕ=1,618033 ...to złoty stosunek. WarunekCwydaje się następujący:„x1,x2,x3są wymienione wFprawie taką samą liczbę razy”.$\frac{|S_{\lnot x_1 \land \lnot x_2}|}{|S_{\lnot x_1 \land \lnot x_2 \land x_3}|} \simeq \phi$

$\phi = 1.618033...$$C$$x_1$$x_2$$x_3$$F$

Aby wykorzystać ten fakt empiryczny, naprawdę chcesz wiedzieć, czy przybliżone liczby mogą dać innym przybliżone liczby. Ale w tym konkretnym przypadku myślę, że może istnieć prosty sposób pokazania, że ​​jest to trudne. Oto szkic.

$T \subset S$$I \cap S = T$$|S|=k$

Zarys dowodu:

1. Jeśli 2-projekcje dają 3-projekcje, dają również k-projekcje w czasie politycznym dla każdego k.
2. Jeśli 2 rzuty dają 4 rzuty, wówczas liczba niezależnych zestawów wykresu jest w FP, więc FP = # P.

$k\geq 3$$x_1,...,x_k,v \in G$${x_1,...,x_k,v}$

$G'$$G'$$G'$${x_1,...,x_k,v}$

${e_1,...,e_m}$$G_k$${e_1,...,e_k}$$G_{k+1}$$G_k$$G_0$$2^{|G|}$

Kilka uwag, a nie odpowiedź.

Zgodnie z uwagą do pytania, dowolna kombinacja 3 literałów może być wyrażona w kategoriach dowolnej innej kombinacji literałów na tych samych zmiennych, wraz z niewielką liczbą terminów, które może dostarczyć wyrocznia. Wynika to z spojrzenia na diagram Venna 3 przecinających się zestawów i wyrażenia każdego z 8 regionów w kategoriach innych regionów. Pamiętaj, że nie wymaga to, aby formuła była monotonna lub 2CNF.

$2^{n-3}$

Stąd pytanie naprawdę dotyczy tego, czy można wykorzystać właściwość bycia monotonicznym 2CNF w celu skompresowania tego wyrażenia wielkości wykładniczej do wielkości wielomianowej.

Próbowałem spojrzeć na prostsze pytanie, ograniczając wyrocznię tylko do ciągu wskazówek z liczbą rozwiązań, gdy liczenie dla literalnych kombinacji pojedynczych lub par nie jest dostępne. Nie widzę żadnego sposobu na wykorzystanie wiedzy o liczbie rozwiązań, aby uzyskać szybkie obliczenie liczby rozwiązań w odniesieniu do dowolnego pojedynczego literału.

$S$$x_1$$|S|$