25 problems

For each integer $k\ge 2$, let $\boldsymbol{F}(k,\alpha)$ denote a random $k$-SAT formula with clause density $\alpha$. Sharp satisfiability threshold conjecture. For every…

For each positive integer $k$, consider random $k$-SAT on $n$ variables, and let its satisfiability threshold be the transition point between satisfiable and unsatisfiable instance…

MAX-SAT and SAT equivalence conjecture. For any $c<0$,

MAX-SAT limiting function conjecture. For every $k$ and every constant $c>0$, as $n\rightarrow\infty$,

Satisfiability threshold conjecture. For each $k$ there exists a threshold density $c_k$, such that for any positive $\varepsilon$, for all $c<c_k-\varepsilon$, $F(n,cn)$ is almost…

Let $N(n,m)$ be the maximum number of clauses that can be satisfied by one assignment of $n$ variables in a random K-SAT instance with $m$ clauses, and let $c^*_K$ be the threshold…

A random K-SAT instance has $n$ Boolean variables and $m=cn$ clauses, where $c$ is the clause-to-variable ratio and $K$ is the number of literals per clause. The linear phase trans…

Large-$k$ critical-exponent conjecture. The exponent $\nu$ tends to $1$ as $k$ tends to infinity.

Let $P(\alpha)$ be the overlap distribution of a random pair of satisfying assignments of a random $k$-SAT formula, and let $P_{\rm ann}(\alpha)$ denote its annealed approximation,…

Let $c_{K,\rm SAT}$ denote the phase-transition point corresponding to the satisfiability threshold in the random $K$-SAT model. Random K-SAT hardness-location conjecture. Hard ins…

Consider structured random combinatorial optimization problems whose instances exhibit phase transitions, including random $K$-SAT. Phase-transition hardness conjecture. The source…

Let $k$ be fixed and let a random $k$-SAT formula have clause density $alpha$. The value $(1+o_k(1))2^k\ln k/k$ is the clustering threshold described in the paper. Algorithmic thre…

Let $\Phi_m(n,k,p)$ be the polarized random $k$-SAT formula with $n$ variables, $m$ clauses, and polarization parameter $p$. For $0\leq p\leq 1$ and $k\geq 3$, let $\alpha_k(p)$ be…

Let $\Phi_m(n,k,p)$ be the polarized random $k$-SAT formula with polarization parameter $p$, and let $\alpha_k(p,n)$ be its median satisfiability threshold. Write $\alpha_k(1/2,n)$…

Fix $k$ and a polarization parameter $p\ff$ with $0\leq p\leq 1$. Let $\Phi_m(n,k,p)$ be the polarized random $k$-SAT formula with $n$ variables and $m$ clauses, and let…

Let $F$ be a random $k$-CNF formula on $n$ Boolean variables with $m$ clauses, and write $alpha=m/n$ for its clause density. A satisfiable formula is one that admits a Boolean assi…

Frozen-variable conjecture. The emergence of frozen variables is the primary cause of algorithmic hardness in random $K$-SAT; moreover, the Backtracking Survey Propagation algorith…

Phase-transition hypothesis. The existence of the sharp satisfiability phase transition itself may be the primary cause of algorithmic hardness in random $K$-SAT.

Low-degree polynomial threshold conjecture. Theorem (and Theorem) holds for all $\kappa > 1$.

Sharp phase transition conjecture. In random $k$-SAT and a wide variety of general constraint satisfaction problems, there is a sharp phase transition: a typical problem is satisfi…

For random 3-SAT on $n$ variables, let $T(\mathbf{X})$ denote the satisfiability threshold. Spin-glass threshold conjecture. The correct threshold is … The paper reports this value…

Let $k\ge k_0$ and $\alpha_{\mathrm{lbd}}\le\alpha\le\alpha_{\mathrm{ubd}}$. Let $\bm{\Omega}$ denote the number of clusters of the random $k$-SAT solution space, and let…

Clustering-obstruction conjecture. The onset of the clustering phase is the main obstruction to finding algorithms that solve such random constraint problems.

Let $\rho$ denote the clause density in a random $k$-SAT formula, let $\theta=1-t/n$ denote the time parameter of the decimation process, and let $\rho_0$ be a constant independent…

Let $\vec\Phi=\vec\Phi_4(n,m)$ be a uniformly random 4-SAT formula with $n$ variables and $m$ clauses. Write $r=m/n$. The random 4-SAT threshold conjecture. The threshold for the e…