Skip to main content
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 ...
Ryan O'Donnell's user avatar
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: ...
smengel's user avatar
  • 176
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.
Whosyourjay's user avatar
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?).
Kaveh's user avatar
  • 21.7k

Only top scored, non community-wiki answers of a minimum length are eligible