Timeline for Compactly representing the solution set of a SAT instance
Current License: CC BY-SA 2.5
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Mar 30, 2011 at 12:57 | history | edited | Giorgio Camerani | CC BY-SA 2.5 |
added 61 characters in body; added 4 characters in body
|
| Mar 30, 2011 at 9:46 | history | edited | Giorgio Camerani | CC BY-SA 2.5 |
edited title
|
| Mar 30, 2011 at 9:40 | history | edited | Giorgio Camerani | CC BY-SA 2.5 |
added 507 characters in body; added 5 characters in body; edited title
|
| Jan 27, 2011 at 13:09 | comment | added | Giorgio Camerani | @Yaroslav: Interesting...could you please elaborate further? | |
| Jan 19, 2011 at 20:28 | comment | added | Yaroslav Bulatov | 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. | |
| Oct 29, 2010 at 15:09 | history | edited | Giorgio Camerani | CC BY-SA 2.5 |
deleted 1 characters in body
|
| Oct 29, 2010 at 14:49 | history | edited | Giorgio Camerani | CC BY-SA 2.5 |
added 242 characters in body
|
| Oct 29, 2010 at 14:39 | history | edited | Giorgio Camerani | CC BY-SA 2.5 |
deleted 1549 characters in body
|
| Oct 13, 2010 at 8:06 | history | edited | Giorgio Camerani | CC BY-SA 2.5 |
added 160 characters in body
|
| Oct 13, 2010 at 7:58 | history | edited | Giorgio Camerani | CC BY-SA 2.5 |
added 593 characters in body; added 14 characters in body
|
| Oct 13, 2010 at 7:21 | answer | added | András Salamon | timeline score: 10 | |
| Oct 12, 2010 at 20:07 | answer | added | Joshua Grochow | timeline score: 9 | |
| Oct 12, 2010 at 19:59 | history | edited | Giorgio Camerani | CC BY-SA 2.5 |
deleted 273 characters in body
|
| Oct 12, 2010 at 19:31 | comment | added | Giorgio Camerani | @Joshua: You're right, thanks. I've enriched the question to clarify. Please let me know if it is OK now. | |
| Oct 12, 2010 at 19:29 | history | edited | Giorgio Camerani | CC BY-SA 2.5 |
Enriched the question to give a better idea of what I'm asking; added 4 characters in body
|
| Oct 12, 2010 at 18:54 | comment | added | Joshua Grochow | 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... | |
| Oct 12, 2010 at 18:34 | history | asked | Giorgio Camerani | CC BY-SA 2.5 |