5 ms·
> As of yet this hunt has not been successful. How current is your information ? I think I've seen random instances in some of the more recent SAT competition
by tgflynn 6y ago
> As of yet this hunt has not been successful.
How current is your information ?
I think I've seen random instances in some of the more recent SAT competitions with only a few thousand variables that have not been solved. That said in theory there should be 100 variable instances that are too hard to solve but I haven't seen any really hard instances that small.
- maweki 6y agoI was in Lissabon Last year at the SAT conference and that was my main takeway, though my field of research is only adjacent. One paper was about creating random sat instances where the probability of unsat ist 50/50 and as it turned out: none of those instances was hard. You can always craft hard instances to defeat a specific heuristic. But crafting one that is hard for all of them is the problem.