We will be presenting a paper of Till Tantau (with the above title), that appeared in CCC 2022.
The Satisfaction Probability $\sigma(\phi)$ of a propositional formula $\phi$ is the probability that a random assignment of variables satisfies the formula. This paper studies the complexity of the problem $k$SAT-PROB$_{>\delta}=\{\phi\in k$CNF$|\sigma(\phi)>\delta\}$ for fixed $k\in\mathbb{N}$ and $\delta\in[0,1]$. While the complexity of a few examples were already known (eg: 3SAT-PROB$_{>0}\in$ NP-Complete), Akmal and Williams have recently showed that 3SAT-PROB$_{>\frac{1}{2}}\in$ P and 4SAT-PROB$_{>\frac{1}{2}}\in$ NP-Complete. In this paper, the author gives a complete characterisation in the form of a trichotomy (i.e. $k$SAT-PROB$_{>\delta}$ is in AC$^0$ or NL-Complete or NP-Complete) based on the parameters $k$ and $\delta$.
