The Proof Complexity of SMT Solvers

From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.

Abstract

The resolution proof system has been enormously helpful in deepening our understanding of conflict-driven clause-learning ( $\(\mathsf {CDCL}\)$ ) SAT solvers. In the interest of providing a similar proof complexity-theoretic analysis of satisfiability modulo theories (SMT) solvers, we introduce a generalization of resolution called Res(T). We show that many of the known results comparing resolution and $\(\mathsf {CDCL}\)$ solvers lift to the SMT setting, such as the result of Pipatsrisawat and Darwiche showing that $\(\mathsf {CDCL}\)$ solvers with “perfect” non-deterministic branching and an asserting clause-learning scheme can polynomially simulate general resolution. We also describe a stronger version of Res(T), $\(\mathsf {Res}^*\)$ (T), capturing SMT solvers allowing introduction of new literals. We analyze the theory EUF of equality with uninterpreted functions, and show that the $\(\mathsf {Res}^*(\mathrm {EUF})\)$ system is able to simulate an earlier calculus introduced by Bjørner and de Moura for the purpose of analyzing $\(\mathsf {DPLL}\)$ (EUF). Further, we show that $\(\mathsf {Res}^*(\mathrm {EUF})\)$ (and thus SMT algorithms with clause learning over EUF, new literal introduction rules and perfect branching) can simulate the Frege proof system, which is well-known to be far more powerful than resolution. Finally, we prove under the Exponential Time Hypothesis (ETH) that any reduction from EUF to SAT (such as the Ackermann reduction) must, in the worst case, produce an instance of size $\(\varOmega (n \log n)\)$ from an instance of size n.