by Allan Sly and Nike Sun

## Random constraint satisfaction problems

Suppose we are given a finite graph. Does it admit a proper three-coloring? This is one example of a *constraint satisfaction problem* (CSP). Generally speaking, a CSP is specified by a list of variables, subject to a set of constraints. A prototypical computational question is to decide, in a given CSP instance, whether there exists any variable assignment satisfying all the constraints. If yes, then one may further ask how many solutions are there, or what is the optimal value of some objective function over the set of solutions.

On general inputs, these questions are not believed to be computationally tractable — many CSPs are NP-complete. For the problem of deciding whether a given graph is three-colorable, the best known algorithms require more than 2^{nϵ} time on the “worst” graphs of size *n*. In view of this, it became natural to develop notions of tractability in “average” or “typical” cases (Levin 1986). One of the standard ways to approach this has been via ensembles of *random CSPs*. For example, say that we sample a large random graph from some natural distribution — might it be the case that “in most cases” it is easy to decide whether the graph is three-colorable?

## Satisfiability transitions in random CSPs

For all the commonly studied random CSP ensembles, the (average-case) complexity remains an open question. A possible reason for this is that even before going into computational considerations, there are far more basic properties of random CSPs that have not been resolved. For example, it seems very difficult to estimate the probability that a random CSP is satisfiable. In many examples, the random CSP can be naturally parametrized by a “constraint level” *α* — commonly, *α* is the ratio of the number of constraints to the number of variables. Numerical experiments (early 1990s) indicated that some of the most canonical random CSPs have a sharp *satisfiability transition* — a critical threshold 0 < *α*_{sat} < ∞ such that the random CSP is satisfiable with high probability for *α* < *α*_{sat}, and unsatisfiable with high probability for *α* > *α*_{sat}.

This transition was most studied for the random *k*-SAT problem, defined as follows. Start with a set of boolean variables *x*_{1},…,*x _{n}*. A

*literal*is a variable

*x*, or its negation ¬

_{i}*x*. For

_{i}*i*≥ 1, the random clause

*a*is the disjunction of

_{i}*k*literals chosen independently and uniformly from the set of literals {

*x*

_{1},¬

*x*

_{1},…,

*x*,¬

_{n}*x*}; the clauses are chosen mutually independently. A

_{n}*random k-SAT formula at density α*is defined by the conjunction of the first

*M*clauses where

*M*is a Poisson(

*nα*) random variable: Φ =

*a*

_{1}∧ … ∧

*a*. Its solution space is the set

_{M}**=**

*S***(Φ) of variable assignments**

*S*__∈ {T,F}__

*x*^{n}which make the formula Φ satisfied, meaning Φ(

__) = T. Let__

*x**p*=

*p*(

_{k}*α,n*) be the probability that the random formula Φ is satisfiable — equivalently,

*p*is the probability for

**to be nonempty. The satisfiability threshold conjecture is that for each**

*S**k*≥ 2, there is a critical

*α*

_{sat}(depending on

*k*but not on

*n*) such that

This was proved for *k* = 2 (with *α*_{sat} = 1) in a few independent works around 1992 (Chvátal–Reed, de la Vega, Goerdt), but remained open for *k* ≥ 3. It is known (Friedgut 1999) that for each *k* ≥ 3 there exists a sharp threshold sequence *α*_{sat}(*n*) — the conjecture holds if the sequence converges.