Timeline for Why do we care about random Boolean SAT formula?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 15, 2015 at 16:07 | comment | added | vzn | oh. see the misconception. randomly generated instances are or are not (always) "quickly" solvable, depending on the "random" distribution. the transition point research explains why to some degree. the "real"/detailed answer must be close to a P=?NP proof. another concept that forgot to mention-- SAT solvers tend to take about the "same amount of time" on the same instances within constant factors. ie SAT solver time is somewhat highly correlated across solvers/ instances. ie apparently theres an instance "hardness" independent of solvers. | |
| Jan 15, 2015 at 7:43 | comment | added | Zack Newsham | Interesting stuff, but (without looking into too much detail at those papers) neither seems to address why we care about random - what does it matter if we can solve random instances quickly, if we can't solve (some) industrial ones at all? | |
| Jan 15, 2015 at 5:41 | comment | added | vzn | in short, a paradigm shift | |
| Jan 14, 2015 at 17:54 | history | answered | vzn | CC BY-SA 3.0 |