7 problems

Let $k\geq 2$, and let $\varphi$ be a random $k$-CNF formula with $m=m(n)$ clauses and $n$ variables, where $m/n\to\alpha$ as $n\to\infty$. The ratio $\alpha$ is the clause density…

Let $k\geq 2$, and let a random $k$-SAT instance have $n$ variables and $m$ clauses, with clauses chosen independently and uniformly with replacement. For a formula, write “satisfi…

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

Chvátal–Reed conjecture. For all $k\geq 2$ there exists a value $\alpha_\mathrm{sat}(k)>0$ such that

Bicycle-dominance conjecture. Either giant bicycles are more probable than small bicycles and the percolation threshold is equal to the phase transition point, or small bicycles ar…

Random $k$-SAT threshold conjecture. For every fixed $k$, there exists a constant $c_k$ such that the satisfiability threshold is asymptotically

Let random 2-iSAT formulas have clause-to-variable ratio $c$. Threshold conjecture. There is a satisfiability threshold at … The value $\frac{3}{2}$ is the one obtained in the pape…