  The satisfaction probability Pr[$\phi$] := Pr$_{\beta:vars(\phi) \to
\{0,1\}}[\beta\models \phi]$ of a propositional formula $\phi$ is the
likelihood that a random assignment $\beta$ makes the formula true. We study
the complexity of the problem $k$SAT-PROB$_{>p}$ = {$\phi$ is a $k$CNF formula
| Pr[$\phi$] > p} for fixed $k$ and $p$. While 3SAT-PROB$_{>0}$ = 3SAT is
NP-complete and SAT-PROB$_{>1/2}$ is PP-complete, Akmal and Williams recently
showed that 3SAT-PROB$_{>1/2}$ lies in P and 4SAT-PROB$_{>1/2}$ is NP-complete;
but the methods used to prove these striking results stay silent about, say,
4SAT-PROB$_{>3/4}$, leaving the computational complexity of $k$SAT-PROB$_{>p}$
open for most $k$ and $p$. In the present paper we give a complete
characterization in the form of a trichotomy: $k$SAT-PROB$_{>p}$ lies in
AC$^0$, is NL-complete, or is NP-complete; and given $k$ and $p$ we can decide
which of the three applies. The proof of the trichotomy hinges on a new
order-theoretic insight: Every set of $k$CNF formulas contains a formula of
maximal satisfaction probability. This deceptively simple statement allows us
to (1) kernelize $k$SAT-PROB$_{\ge p}$, (2) show that the variables of the
kernel form a backdoor set when the trichotomy states membership in AC$^0$ or
NL, and (3) prove a locality property by which Pr[$\phi$] < $p$ implies, for
$k$CNF formulas $\phi$, that Pr[$\psi$] < $p$ holds already for some fixed-size
subset $\psi$ of $\phi$'s clauses.
