10
$\begingroup$

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:

  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'$)
$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – Joshua Grochow Oct 12 '10 at 18:54
  • $\begingroup$ @Joshua: You're right, thanks. I've enriched the question to clarify. Please let me know if it is OK now. $\endgroup$ – Giorgio Camerani Oct 12 '10 at 19:31
  • $\begingroup$ 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. $\endgroup$ – Yaroslav Bulatov Jan 19 '11 at 20:28
  • $\begingroup$ @Yaroslav: Interesting...could you please elaborate further? $\endgroup$ – Giorgio Camerani Jan 27 '11 at 13:09
10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @András: I've added a clarification section. $\endgroup$ – Giorgio Camerani Oct 13 '10 at 8:02
  • $\begingroup$ @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). $\endgroup$ – Giorgio Camerani Oct 13 '10 at 10:32
  • $\begingroup$ @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. $\endgroup$ – Giorgio Camerani Oct 29 '10 at 13:45
  • $\begingroup$ @Walter: might be worth editing the question in line with that reformulation, or posting a new question. $\endgroup$ – András Salamon Oct 29 '10 at 14:09
  • $\begingroup$ @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?). $\endgroup$ – Giorgio Camerani Oct 29 '10 at 15:07
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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$? $\endgroup$ – Giorgio Camerani Oct 13 '10 at 7:15
  • $\begingroup$ @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. $\endgroup$ – Giorgio Camerani Oct 13 '10 at 8:10
  • $\begingroup$ @Walter: I did indeed mean $R$ in the third-to-last line. $\endgroup$ – Joshua Grochow Oct 13 '10 at 19:51
  • $\begingroup$ @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. $\endgroup$ – Joshua Grochow Oct 13 '10 at 19:53
  • $\begingroup$ @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. $\endgroup$ – Joshua Grochow Oct 13 '10 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.