7 problems

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…

For given $n$, $k\geq2$, and $p$, let $F_k(n,p)$ be the random $k$-SAT formula obtained by including each of the $\binom{2n}{k}$ possible $k$-clauses independently with probability…

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