Compactly representing the solution set of a SAT instance

Question

This question has risen in my mind after reading András Salamon's and Colin McQuillan's contributions to my previous question Counting solutions of Monotone-2CNF formulas.

EDIT 30^th Mar 2011
Added question n° 2.

EDIT 29^th Oct 2010
Question rephrased after András proposal to formalize it through the notion of nice representation of a solution set (I've modified his notion a little bit).

Let $F$ be a generic CNF formula with $n$ variables. Let $S$ be its solution set. Clearly, $|S|$ may be exponential in $n$. Let $R$ be a representation of $S$. $R$ is said to be nice if and only if the following facts are all true:

1. $R$ has polynomial size in $n$.
2. $R$ allows to enumerate the solutions in $S$ with polynomial delay.
3. $R$ allows to determine $|S|$ in polynomial time (i.e. without enumerating all the solutions).

It would be great if it is possible, in polynomial time, to build such a $R$ for every formula.

Questions:

1. Did anyone ever prove that there exists a family of formulas for which such a nice representation can't exist?
2. Did anyone study the relationship between the representation of $S$ and the symmetries exhibited by $F$? Intuitively, symmetries should help to compactly represent $S$ because they avoid the explicit representation of a solution subset $S' \subset S$ when $S'$ actually boils down to just one solution (i.e. from every $s_i \in S'$ you can recover every other $s_j \in S'$ by applying a proper symmetry, thus every $s_i \in S'$ is itself representative of the whole $S'$)

Answer 1

As stated (revision 3), the question has a simple answer: no.

The reason is that even for the highly restricted class of representations given by Boolean circuits with AND, OR, and NOT gates, no nontrivial lower bounds are known. (Clearly a circuit that represents $F$ will also represent $S$ implicitly, and it is easy to enumerate the solutions by changing the inputs to the circuit.)

For even more restricted representations, like monotone or constant depth circuits, exponential lower bounds are known. There are also exponential lower bounds for representing formulas in CNF or DNF form, although these can be seen as special cases of constant depth circuits. Finally, BDD representations can be seen as compact forms of DNF, but there exist formulas for which the BDD requires exponential size for any variable ordering.

To make your question more precise, please consider @Joshua's answer in some detail, and please clarify what you mean by "trivial to enumerate every single solution".

---

For revision 4, note the statement about BDD size. Part of what you seem to be asking is: is there a more compact representation of DNF formulas than BDDs? Let "BDD $B$ has superpolynomial size" mean "every BDD representing the same function as $B$, regardless of variable ordering, has superpolynomial size", and let "nice representation" mean "a representation that allows solutions to be enumerated with polynomial delay". This more specific question then becomes:

is there a family of formulas and a nice representation that has polynomial size while its BDDs have superpolynomial size?

Does this capture the essence of what you are asking?

Answer 2

[This answer was in response to the version prior to Revision 6 of 29 Oct 2010.]

I think the question more-or-less works now, but there is a technical issue remaining. Namely, how to formalize "it is trivial to enumerate every single solution by just looking at such structure." A perhaps naive formalization (but the only one I could come up with at the moment) is as follows: let $R(\varphi)$ denote the representation of the solution set $S(\varphi)$ of $\varphi$. At the moment I put no restriction on $R$ other than that $|R(\varphi)| \leq poly(n)$ where $\varphi$ is a CNF on $n$ variables. Then we want there to be an algorithm $A$ such that $A(R(\varphi)) = S(\varphi)$ and $A$ on input $R(\varphi))$ runs in time $poly(n, |S|)$.

Under this formalization, the only difficult cases are the ones where $S$ is super-polynomial but sub-exponential. The remaining cases are handled by the following representation $R$ and algorithm $A$: if $|S| \leq poly(n)$, then let $R(\varphi) = (0, S)$. If $|S| \geq 2^{\Omega(n)}$ then let $R(\varphi) = (1, \varphi)$. $A(0, S)$ simply outputs $S$, and $A(1, \varphi)$ simply computes $S$ by brute force from $\varphi$. Since $|S| = 2^{\Omega(n)}$ in the latter case, this still runs in time $O(|S|)$.

However, the difficult cases are in general impossible under this formalization. If such an $R$ and $A$ existed, it would mean that the $p$-time-bounded Kolmogorov complexity of every $S$ was bounded by $poly(n)$, which is absurd (since almost all sets $S$ have maximal $p$-time-bounded Kolmogorov complexity, namely $|S|$). (Here $p$ is the running time of $A$ as a function of $|S|$.)

(Note that if we additionally require that $R$ run in time $poly(n, |\varphi|)$, then the answer to the question is no in general, assuming $P \neq PromiseUP$: if $\varphi$ has a unique solution, then $A(R(\varphi))$ would solve $\varphi$ and run in time $poly(n)$.