The Monasson et al. mixed 2- and 3-SAT threshold conjecture

Let F2,3(n,m1,m2)F_{2,3}(n,m_1,m_2) be the conjunction of independent random 22-SAT and 33-SAT formulas with the indicated numbers of clauses. Set m1=α2nm_1=\alpha_2 n, m2=α3nm_2=\alpha_3 n, let p=α3/(α2+α3)p=\alpha_3/(\alpha_2+\alpha_3), and write α=α2+α3\alpha=\alpha_2+\alpha_3.

Monasson et al.'s mixed-SAT conjecture. For every p[0,1]p\in[0,1] there exists a value αsat(2+p)>0\alpha_\mathrm{sat}(2+p)>0 such that, whenever α2,α3>0\alpha_2,\alpha_3>0 satisfy α3/(α2+α3)=p\alpha_3/(\alpha_2+\alpha_3)=p,

limnP(F2,3(n,α2n,α3n) is satisfiable)={1,if α<αsat(2+p),0,if α>αsat(2+p).\lim_{n\to\infty}\mathbb P(F_{2,3}(n,\alpha_2 n,\alpha_3 n)\text{ is satisfiable})=\begin{cases}1,&\text{if }\alpha<\alpha_\mathrm{sat}(2+p),\\\\0,&\text{if }\alpha>\alpha_\mathrm{sat}(2+p). \end{cases}

Furthermore, for p<0.413p<0.413\dots one has αsat(2+p)=αsat(2)/(1p)\alpha_\mathrm{sat}(2+p)=\alpha_\mathrm{sat}(2)/(1-p), whereas this equality does not hold for p0.413p\geq0.413\dots. 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.