Timeline for Survey of transformations related to the use of SAT solvers
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 20, 2012 at 0:56 | comment | added | vzn | yes SAT is amazing in how many problems can be translated to it, but unless your problem is rather unusual, it might have its own [more efficient] methods in the literature. translating to SAT is interesting to study "why" problem instances are hard or easy based on its constraint graph structure, but not always such a good idea to get the fastest algorithmic solution. another rule of thumb is to estimate how many clauses/variables your instances will have and compare that to known benchmarks of the algorithms. | |
| Apr 28, 2011 at 13:14 | vote | accept | Anthony Labarre | ||
| Apr 21, 2011 at 12:58 | answer | added | Anthony Labarre | timeline score: 9 | |
| Apr 8, 2011 at 17:27 | comment | added | Mikolas | this question might be somewhat related: cstheory.stackexchange.com/q/4314/4506 | |
| Apr 5, 2011 at 18:54 | comment | added | Mikolas | It sounds a little bit confusing that you are talking about an optimization prob but at the same time about SAT. Typically for optimality you need something stronger, e.g. MAX-SAT. Maybe you could clarify that. | |
| Apr 5, 2011 at 18:44 | answer | added | Mikolas | timeline score: 10 | |
| Apr 5, 2011 at 17:34 | history | edited | Suresh Venkat |
edited tags
|
|
| Apr 5, 2011 at 16:24 | comment | added | Giorgio Camerani | Don't worry, it is the right word, I should have understood that. From a purely practical point of view, however, I don't think that it matters (what matters most is how parsimonious your encoding is). Could you provide some further details on the optimization problem you're trying to solve? I'm very interested in practical applications of SAT and in the engineering aspects of SAT solving. | |
| Apr 5, 2011 at 14:46 | comment | added | Anthony Labarre | @Walter: Sorry if this is not the right word, I meant things like $k$-SAT, Planar-SAT, NAE-SAT, and so on... but I should probably enclose those two words between parentheses, since I don't know whether that matters when using SAT solvers. | |
| Apr 5, 2011 at 14:41 | comment | added | Giorgio Camerani | What do you exactly mean by "variants of SAT"? | |
| Apr 5, 2011 at 14:30 | history | tweeted | twitter.com/#!/StackCSTheory/status/55276104721764352 | ||
| Apr 5, 2011 at 13:46 | history | asked | Anthony Labarre | CC BY-SA 2.5 |