4 ms·
SAT solvers are not fast on average. Even some very simple random distributions produce small (<100 variables) SAT instances that are very hard for the solvers.
by Laakeri 7y ago
SAT solvers are not fast on average. Even some very simple random distributions produce small (<100 variables) SAT instances that are very hard for the solvers.
- tgflynn 7y agoDo you have a link ? I've been on the lookout for small hard SAT instances for some time and haven't really found any.
- Laakeri 7y agoSAT competition 2018 http://sat2018.forsyte.tuwien.ac.at/index.php http://sat2018.forsyte.tuwien.ac.at/index.php had a track with random instances. The article "Generating the Uniform Random Benchmarks" in https://helda.helsinki.fi/bitstream/handle/10138/237063/sc2018_proceedings.pdf https://helda.helsinki.fi/bitstream/handle/10138/237063/sc20... contains the descriptions of the random instances used.
- tgflynn 7y agoThanks for the link, but it seems difficult to answer the question "find a SAT instance with no more than 100 variables which all competing solvers failed to solve in the allowed time" from the information presented here. I'm going to download the benchmarks and try to correlate them with the results CSV table (which doesn't show number of variables for each instance), but since the full random benchmarks are 2.9 GB compressed this might take a fair amount of work. If you can provide any further guidance on finding the relevant instances I'd appreciate it.
- tgflynn 7y agoAlso note that just specifying the number of variables may not be terribly informative if you don't also specify the maximum clause size and the number of clauses. For example I see some instances here with 120 variables but they are 7-SAT with around 10k clauses. Unless I'm mistaken reducing those to <=3-SAT will require adding about 20k more variables and tripling the number of clauses.