Timeline for Compactly representing the solution set of a SAT instance
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 29, 2010 at 16:12 | comment | added | András Salamon | @Walter: yes, it was just a placeholder term. | |
| Oct 29, 2010 at 15:07 | comment | added | Giorgio Camerani | @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?). | |
| Oct 29, 2010 at 14:09 | comment | added | András Salamon | @Walter: might be worth editing the question in line with that reformulation, or posting a new question. | |
| Oct 29, 2010 at 13:45 | comment | added | Giorgio Camerani | @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. | |
| Oct 13, 2010 at 10:32 | comment | added | Giorgio Camerani | @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). | |
| Oct 13, 2010 at 9:34 | history | edited | András Salamon | CC BY-SA 2.5 |
address edit
|
| Oct 13, 2010 at 8:02 | comment | added | Giorgio Camerani | @András: I've added a clarification section. | |
| Oct 13, 2010 at 7:21 | history | answered | András Salamon | CC BY-SA 2.5 |