  In this short paper we present a survey of some results concerning the random
SAT problems. To elaborate, the Boolean Satisfiability (SAT) Problem refers to
the problem of determining whether a given set of $m$ Boolean constraints over
$n$ variables can be simultaneously satisfied, i.e. all evaluate to $1$ under
some interpretation of the variables in $\{ 0,1\}$. If we choose the $m$
constraints i.i.d. uniformly at random among the set of disjunctive clauses of
length $k$, then the problem is known as the random $k$-SAT problem. It is
conjectured that this problem undergoes a structural phase transition; taking
$m=\alpha n$ for $\alpha>0$, it is believed that the probability of there
existing a satisfying assignment tends in the large $n$ limit to $1$ if
$\alpha<\alpha_\mathrm{sat}(k)$, and to $0$ if $\alpha>\alpha_\mathrm{sat}(k)$,
for some critical value $\alpha_\mathrm{sat}(k)$ depending on $k$. We review
some of the progress made towards proving this and consider similar conjectures
and results for the more general case where the clauses are chosen with varying
lengths, i.e. for the so-called random mixed SAT problems.

Probability;Computational Complexity