The Monasson et al. mixed 2- and 3-SAT threshold conjecture
The Monasson et al. mixed 2- and 3-SAT threshold conjecture
Let be the conjunction of independent random -SAT and -SAT formulas with the indicated numbers of clauses. Set , , let , and write .
Monasson et al.'s mixed-SAT conjecture. For every there exists a value such that, whenever satisfy ,
Furthermore, for one has , whereas this equality does not hold for . The conjecture extends the proposed sharp threshold picture to mixed clause models; the source reports the stated threshold relation as part of the conjectural claim.
Sources & referencesView supporting material
Primary source
Andreas Basse-O'Connor, Tobias Lindhardt Overgaard and Mette Skjøtt, “Some Results on Random Mixed SAT Problems”, arXiv:2311.02644 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.