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 30th Mar 2011
Added question n° 2.
EDIT 29th 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:
- $R$ has polynomial size in $n$.
- $R$ allows to enumerate the solutions in $S$ with polynomial delay.
- $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.
- Did anyone ever prove that there exists a family of formulas for which such a nice representation can't exist?
- 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'$)