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

<p>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|)$.</p>

<p>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|)$.</p>

<p>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|$.)</p>

<p>(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)$.</p>

CC BY-SA 2.5
2010-10-13T07:15:00.490Z
@Joshua: Thank you for dedicating some of your time to answer this question. Maybe in the third last line we should replace $R$ with $A$?
Giorgio Camerani
CC BY-SA 2.5
2010-10-13T08:10:08.173Z
@Joshua: I think the "problem" with $R(\varphi) = (1,\varphi)$ is that it requires brute force. It's not trivial for a human being (nor for an algorithm) to immediately "see" the satisfying assignments by just looking at it.
Giorgio Camerani
CC BY-SA 2.5
2010-10-13T19:51:13.233Z
@Walter: I did indeed mean $R$ in the third-to-last line.
Joshua Grochow
CC BY-SA 2.5
2010-10-13T19:53:10.733Z
@Walter: I fully recognize that $R(\varphi) = (1, \varphi)$ violates the spirit of your question, at least partially (since I only do this for some, not all, formulae). This is part of the technical issue: the only way I could think of to formalize your question allows silly things like this, which partially violate the spirit of the question. Finding a formalization that does not allow this would be quite interesting.
Joshua Grochow
CC BY-SA 2.5
2010-10-13T19:55:54.177Z
@Walter, @András Salamon: Perhaps Andras's suggestion of outputting the elements of $S$ with polynomial (in $n$) delay (rather than in time $O(|S|)$) would be a better formalization.  It certainly rules out things like $R(\varphi) = (1, \varphi)$, even when $\varphi$ has exponentially many solutions.
Joshua Grochow
CC BY-SA 2.5
2010-10-29T13:54:22.133Z
@Joshua: Yes, as I said in a comment to András, his notion of nice representation (polynomial size together with polynomial delay) very well captures my (vague) idea. I wonder if the polynomial size constraint can be achieved through a clever use of symmetries.
Giorgio Camerani
CC BY-SA 2.5
2010-10-12T20:07:12.700Z
2010-10-29T17:42:07.963Z
2010-10-29T17:42:07.963Z
Joshua Grochow
<p>As stated (revision 3), the question has a simple answer: no.</p>

<p>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.)</p>

<p>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.</p>

<p>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".</p>

<hr>

<p>For revision 4, note the statement about BDD size.  Part of what you seem to be asking is: is there a <em>more compact</em> 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:</p>

<blockquote>
  <p>is there a family of formulas and a nice representation that has polynomial size while its BDDs have superpolynomial size?</p>
</blockquote>

<p>Does this capture the essence of what you are asking?</p>

CC BY-SA 2.5
2010-10-13T08:02:32.770Z
@András: I've added a clarification section.
Giorgio Camerani
CC BY-SA 2.5
2010-10-13T10:32:35.437Z
@András: I do apologize if my question lacks precision. Your sentence _"is there a more compact representation of DNF formulas than BDDs?"_ captures the essence of what I'm asking. Such more compact representation would have to be possible for every formula (even those having a superpolynomial number of solutions).
Giorgio Camerani
CC BY-SA 2.5
2010-10-29T13:45:05.483Z
@András: Hi, I've thought a bit more about it. A better capturing of the essence of what I'm asking is the question _"Is there a nice representation that has polynomial size for every formula?"_. Such representation has to be the "best ever", regardless of how BDDs behave compared to it. Your suggestion of polynomial delay fits perfectly with the idea I have in mind.
Giorgio Camerani
CC BY-SA 2.5
2010-10-29T14:09:59.217Z
@Walter: might be worth editing the question in line with that reformulation, or posting a new question.
András Salamon
CC BY-SA 2.5
2010-10-29T15:07:52.540Z
@András: I've rephrased the question. The definition of _nice representation_ has been changed a bit (I've assumed it was a term of your invention rather than a term well established in the literature, isn't it?).
Giorgio Camerani
CC BY-SA 2.5
2010-10-29T16:12:42.277Z
@Walter: yes, it was just a placeholder term.
András Salamon
CC BY-SA 2.5
2010-10-13T07:21:08.557Z
2010-10-13T09:34:30.710Z
2010-10-13T09:34:30.710Z
András Salamon
<p>This question has risen in my mind after reading András Salamon's and Colin McQuillan's contributions to my previous question <a href="https://cstheory.stackexchange.com/questions/2106/counting-solutions-of-monotone-2cnf-formulas">Counting solutions of Monotone-2CNF formulas</a>. 
<br><br>
EDIT 30<sup>th</sup> Mar 2011<br>
Added question n° 2.<br><br>
EDIT 29<sup>th</sup> Oct 2010<br>
Question rephrased after András proposal to formalize it through the notion of <em>nice representation of a solution set</em> (I've modified his notion a little bit).
<br><br>
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 <em>nice</em> if and only if the following facts are all true:</p>

<ol>
<li>$R$ has polynomial size in $n$.</li>
<li>$R$ allows to enumerate the solutions in $S$ with polynomial delay.</li>
<li>$R$ allows to determine $|S|$ in polynomial time (i.e. without enumerating all the solutions).
</ol>

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

<blockquote>
  <p><strong>Questions:</strong></p>
  
  <ol>
  <li>Did anyone ever prove that there exists a family of formulas for which such a <i>nice</i> representation can't exist?</li>
  <li>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'$)</li>
  </ol> 
</blockquote>

CC BY-SA 2.5
2011-01-19T20:28:35.090Z
BTW, one way to represent solution set is an "AND/OR search tree". Each instance is a leaf of the tree, and counting can be done without enumerating all the solutions.
Yaroslav Bulatov
CC BY-SA 2.5
2011-01-27T13:09:43.387Z
@Yaroslav: Interesting...could you please elaborate further?
Giorgio Camerani
CC BY-SA 2.5
2010-10-12T18:54:09.060Z
I think you need to restrict your question a little.  As stated, the formula $F$ itself is a polynomial-sized representation of $S$.  But this obviously does not help for the motivation coming from the previous problem.  Maybe you want some bound (polynomial?) on the complexity of reproducing $S$ (or maybe a single element of $S$, or computing $|S|$) from the polynomial-sized representation...
Joshua Grochow
CC BY-SA 2.5
2010-10-12T19:31:36.333Z
@Joshua: You're right, thanks. I've enriched the question to clarify. Please let me know if it is OK now.
Giorgio Camerani
<cc.complexity-theory><ds.algorithms><sat><counting-complexity>
Compactly representing the solution set of a SAT instance
Giorgio Camerani
# Compactly representing the solution set of a SAT instance

(Asked by: username_0 on 2010-10-12)

This question has risen in my mind after reading username_3's and Colin McQuillan's contributions to my previous question [Counting solutions of Monotone-2CNF formulas](https://cstheory.stackexchange.com/questions/2106/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:

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'$)

**Tags:** cc.complexity-theory, ds.algorithms, sat, counting-complexity

> **Comments:**
> **username_2**: I think you need to restrict your question a little.  As stated, the formula $F$ itself is a polynomial-sized representation of $S$.  But this obviously does not help for the motivation coming from the previous problem.  Maybe you want some bound (polynomial?) on the complexity of reproducing $S$ (or maybe a single element of $S$, or computing $|S|$) from the polynomial-sized representation...  
> **username_0**: @Joshua: You're right, thanks. I've enriched the question to clarify. Please let me know if it is OK now.  
> **username_1**: BTW, one way to represent solution set is an "AND/OR search tree". Each instance is a leaf of the tree, and counting can be done without enumerating all the solutions.  
> **username_0**: @Yaroslav: Interesting...could you please elaborate further?  

---

## 2 answers

### Answer by username_3 on 2010-10-13. Score: 10

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?

> **Comments:**
> **username_0**: @András: I've added a clarification section.  
> **username_0**: @András: I do apologize if my question lacks precision. Your sentence _"is there a more compact representation of DNF formulas than BDDs?"_ captures the essence of what I'm asking. Such more compact representation would have to be possible for every formula (even those having a superpolynomial number of solutions).  
> **username_0**: @András: Hi, I've thought a bit more about it. A better capturing of the essence of what I'm asking is the question _"Is there a nice representation that has polynomial size for every formula?"_. Such representation has to be the "best ever", regardless of how BDDs behave compared to it. Your suggestion of polynomial delay fits perfectly with the idea I have in mind.  
> **username_3**: @Walter: might be worth editing the question in line with that reformulation, or posting a new question.  
> **username_0**: @András: I've rephrased the question. The definition of _nice representation_ has been changed a bit (I've assumed it was a term of your invention rather than a term well established in the literature, isn't it?).  
> **username_3**: @Walter: yes, it was just a placeholder term.  

---

### Answer by username_2 on 2010-10-12. Score: 9

[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)$.

> **Comments:**
> **username_0**: @Joshua: Thank you for dedicating some of your time to answer this question. Maybe in the third last line we should replace $R$ with $A$?  
> **username_0**: @Joshua: I think the "problem" with $R(\varphi) = (1,\varphi)$ is that it requires brute force. It's not trivial for a human being (nor for an algorithm) to immediately "see" the satisfying assignments by just looking at it.  
> **username_2**: @Walter: I did indeed mean $R$ in the third-to-last line.  
> **username_2**: @Walter: I fully recognize that $R(\varphi) = (1, \varphi)$ violates the spirit of your question, at least partially (since I only do this for some, not all, formulae). This is part of the technical issue: the only way I could think of to formalize your question allows silly things like this, which partially violate the spirit of the question. Finding a formalization that does not allow this would be quite interesting.  
> **username_2**: @Walter, @username_3: Perhaps Andras's suggestion of outputting the elements of $S$ with polynomial (in $n$) delay (rather than in time $O(|S|)$) would be a better formalization.  It certainly rules out things like $R(\varphi) = (1, \varphi)$, even when $\varphi$ has exponentially many solutions.  
> **username_0**: @Joshua: Yes, as I said in a comment to András, his notion of nice representation (polynomial size together with polynomial delay) very well captures my (vague) idea. I wonder if the polynomial size constraint can be achieved through a clever use of symmetries.  

---

