Efficient score computation tied to Boolean satisfiability remains challenging
Pointwise Score Evaluation from Succinct Boolean Descriptions: SAT Equivalence for Strongly Log-Concave Gaussian Mixtures
Computational Complexity
Summary
This paper looks at how hard it is to calculate certain probabilities (called scores) for complex mixtures of normal distributions described by yes/no conditions. The authors find that even when these mixtures have nice smooth shapes, figuring out the score at one point is as hard as solving a famous tough problem in computer science, called Boolean satisfiability. This means that just having a smooth shape doesn't make these calculations easy, and finding a quick method to compute these scores remains an open question.
What this means in practice
- •For machine learning engineers: Understand fundamental limits when designing score-based generative models involving complex constraints represented as Boolean formulas.
- •For cryptography developers: Use hardness of score evaluation equivalences to explore new cryptographic assumptions based on Gaussian mixtures with Boolean structure.
A theory result. No direct application yet.
Authors
Yinzhen Lv
Abstract
Score-based generative models rely on access to accurate scores, but the cost of computing those scores depends on how the underlying distribution is represented. Can smoothness and strong log-concavity make score evaluation efficient when a distribution is specified by Boolean constraints? I investigate this question by separating geometric encoding from computational extraction. I construct a succinctly specified Gaussian mixture whose score at a fixed query location encodes whether a Boolean formula is satisfiable. The construction has rational component means and uniform strong log-concavity, yet deterministic polynomial-time approximation of the designated score coordinate to constant absolute accuracy is equivalent to polynomial-time solvability of Boolean satisfiability. This equivalence remains valid throughout a neighborhood whose radius is independent of dimension. I further characterize how numerical precision connects bounded witness enumeration to exact counting, and show that independent sample access turns the same target into a dimension-independent mean-estimation problem. An explicit parity construction also separates low-degree approximation from efficient computation. Together, these results show that favorable geometry alone does not resolve the computational cost of extracting scores from compact descriptions. They identify the precise extraction requirement in this formulation while leaving the existence of a general efficient evaluator open.