Kompaktowo reprezentujący zestaw rozwiązań instancji SAT

To pytanie pojawiło się w mojej głowie po przeczytaniu wkładów Andrása Salamona i Colina McQuillana w moje poprzednie pytanie. Liczenie rozwiązań formuł Monotone-2CNF .

EDIT 30 ^th mar 2011
Dodano Pytanie nr 2.

EDIT 29 ^th Paź 2010
Pytanie rephrased po wniosku András sformalizowania go poprzez pojęcia miły reprezentacji zbioru rozwiązań (I zostały zmodyfikowane jego pojęcie trochę).

Niech będzie ogólną formułą CNF z zmiennymi. Niech będzie jego rozwiązaniem. Oczywiście,może być wykładniczy w . Niechn S | S | n $F$$n$$S$$|S|$$n$$R$jest przedstawienie . Mówi się, że jest miły tylko wtedy, gdy wszystkie poniższe fakty są prawdziwe:$S$$R$

1. $R$ ma wielomian w .$n$
2. $R$ pozwala wyliczyć rozwiązania w z opóźnieniem wielomianowym.$S$
3. $R$ pozwala określićw czasie wielomianowym (tj. bez wyliczenia wszystkich rozwiązań). $|S|$

Byłoby wspaniale, gdyby w czasie wielomianowym było możliwe zbudowanie takiego dla każdej formuły.$R$

Pytania:

1. Czy ktokolwiek kiedykolwiek udowodnił, że istnieje rodzina formuł, dla której tak ładna reprezentacja nie może istnieć?
2. Czy ktoś badał związek między reprezentacją a symetriami wykazanymi przez ? Intuicyjnie symetrie powinny pomóc w kompaktowym przedstawieniu ponieważ unikają jawnej reprezentacji podzbioru rozwiązania gdy faktycznie sprowadza się do tylko jednego rozwiązania (tj. Z każdego można odzyskać co drugi poprzez zastosowanie odpowiedniej symetrii, a zatem każdy sam jest reprezentatywny dla całego )F S S ′ ⊂ S S ′ s i ∈ S ′ s j ∈ S ′ s i ∈ S ′ S $S$$F$$S$$S' \subset S$$S'$$s_i \in S'$$s_j \in S'$$s_i \in S'$$S'$

Jak stwierdzono (wersja 3), pytanie ma prostą odpowiedź: nie.

Powodem jest to, że nawet dla wysoce ograniczonej klasy reprezentacji podanej przez obwody boolowskie z bramkami AND, OR i NOT, nie są znane nietrywialne dolne granice. (Oczywiście obwód reprezentujący będzie również reprezentował domyślnie i łatwo jest wymienić rozwiązania, zmieniając wejścia do obwodu.)$F$$S$

W przypadku jeszcze bardziej ograniczonych reprezentacji, takich jak obwody monotoniczne lub o stałej głębokości, znane są wykładnicze dolne granice. Istnieją również wykładnicze dolne granice reprezentowania wzorów w postaci CNF lub DNF, chociaż można je postrzegać jako specjalne przypadki obwodów o stałej głębokości. Wreszcie reprezentacje BDD można postrzegać jako zwarte formy DNF, ale istnieją formuły, dla których BDD wymaga wykładniczej wielkości dla dowolnej kolejności zmiennych.

Aby uściślić swoje pytanie, rozważ szczegółowo odpowiedź Jozuego i wyjaśnij, co rozumiesz przez „trywialne wyliczenie każdego pojedynczego rozwiązania”.

W przypadku wersji 4 zwróć uwagę na informację o rozmiarze BDD. Wydaje się, że pytasz częściowo: czy istnieje bardziej zwarta reprezentacja formuł DNF niż BDD? Niech „BDD ma rozmiar wielobiegunowy” oznacza „każdy BDD reprezentujący tę samą funkcję co , niezależnie od kolejności zmiennych, ma rozmiar wielobiegunowy”, i niech „ładna reprezentacja” oznacza „reprezentację, która pozwala na policzenie rozwiązań z opóźnieniem wielomianowym”. To bardziej szczegółowe pytanie staje się następnie:$B$$B$

czy istnieje rodzina formuł i ładna reprezentacja, która ma rozmiar wielomianowy, a jego dyski BDD mają rozmiar wielobiegunowy?

Czy to oddaje istotę tego, o co pytasz?

[Ta odpowiedź była odpowiedzią na wersję sprzed wersji 6 z 29 października 2010 r.]

$R(\varphi)$$S(\varphi)$$\varphi$$R$$|R(\varphi)| \leq poly(n)$$\varphi$$n$$A$$A(R(\varphi)) = S(\varphi)$$A$$R(\varphi))$$poly(n, |S|)$

$S$$R$$A$$|S| \leq poly(n)$$R(\varphi) = (0, S)$$|S| \geq 2^{\Omega(n)}$$R(\varphi) = (1, \varphi)$$A(0, S)$$S$$A(1, \varphi)$$S$$\varphi$$|S| = 2^{\Omega(n)}$$O(|S|)$

$R$$A$$p$$S$$poly(n)$$S$$p$$|S|$$p$$A$$|S|$

$R$$poly(n, |\varphi|)$$P \neq PromiseUP$$\varphi$$A(R(\varphi))$$\varphi$$poly(n)$