10
votes
Accepted
Random 3-SAT: What is the consensus experimental range of the threshold?
In light of the Ding--Sly--Sun verification of the 1-step Replica Symmetry Breaking picture for kSAT (when k is large enough) I think experts would now be pretty surprised if the MPZ/MMZ-conjectured ...
- 1,791
6
votes
Accepted
How to benchmark #2-SAT counting algorithms?
I am not aware of any collections of 2CNF benchmark instances.
However, one practical way of constructing #2-SAT instances that are provably hard for state-of-the-art model counters is as follows: ...
- 146
2
votes
Generating hard satisfiability problems with given constraint graph
It sounds like what you want are universal factor graphs. Such graphs exist for every NP-hard boolean CSP and in many cases are optimally inapproximable.
- 513
1
vote
Lower bound for proving a random 3-SAT formula is unsat?
See Jan Krajicek, "A note on SAT algorithms and proof complexity", 2012
I am not sure if we have any result for random unsat instances (how do you define a random unsat instance?).
- 21.4k
Only top scored, non community-wiki answers of a minimum length are eligible