The MAX-SAT and SAT equivalence conjecture
The MAX-SAT and SAT equivalence conjecture
Let be a uniformly random -SAT formula with variables and clauses, and let denote the expected maximum number of satisfiable clauses. For a fixed density , consider the limiting expected satisfiable fraction and the limiting probability of satisfiability.
MAX-SAT and SAT equivalence conjecture. For any ,
if and only if
The conjecture is intended to formalize a connection between the MAX-SAT limiting function conjecture and the usual satisfiability threshold conjecture. The source provides no resolution status beyond presenting it as a conjecture.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Don Coppersmith, David Gamarnik, Mohammad Hajiaghayi and Gregory B. Sorkin, “Random MAX SAT, Random MAX CUT, and Their Phase Transitions”, arXiv:math/0306047 (2003).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.