8 problems

Let $F(n,cn)$ be a random 3-CNF formula with $n$ variables and clause-to-variable density $c$, and let $c_3$ denote the threshold constant from the Satisfiability Threshold Conject…

Let $F(n,cn)$ be a random $k$-CNF formula with $n$ variables and clause-to-variable density $c$, formed from $m=cn$ independently and uniformly selected proper clauses of length…

Threshold convergence conjecture. The sequence $d_n$ converges to a limit $d_c$.

Let $F_k(n,m)$ be the random $k$-SAT formula on $n$ variables with $m$ uniformly chosen clauses, and write the clause density as $4\alpha=m/n4$. Satisfiability threshold conjecture…

For the Coloring, K-SAT and NAE-K-SAT models, let $p(N,M)$ be the probability that an instance with $N$ variables or vertices and $M$ edges or clauses is colorable or satisfiable.…

For each of the Coloring, K-SAT and NAE-K-SAT models, let $p(N,M)$ denote the probability that an instance with $N$ variables or vertices and $M$ edges or clauses is colorable or s…

Consider a uniformly random instance of a $K$-SAT problem on $N$ variables with $cN$ clauses, and let the number of satisfiable clauses be maximized over all assignments. Copeland–…

Let ${\cal{P}}^{{\rm sat}}_{n,m}$ be the random satisfiable process on $n$ variables with $m$ clauses, and let $d=m/n$ denote the clause density. A phase transition for satisfiabil…