Paper Info
Title
The Proof Complexity Of Smt Solvers
Abstract
The resolution proof system has been enormously helpful in deepening our understanding of conflict-driven clause-learning (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 CDCL solvers lift to the SMT setting, such as the result of Pipatsrisawat and Darwiche showing that 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), Res*(T), capturing SMT solvers allowing introduction of new literals. We analyze the theory EUF of equality with uninterpreted functions, and show that the Res* (EUF) system is able to simulate an earlier calculus introduced by Bjorner and de Moura for the purpose of analyzing DP LL(EUF). Further, we show that Res* (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 Omega(n log n) from an instance of size n.
Year
DOI
Venue
2018
10.1007/978-3-319-96142-2_18
COMPUTER AIDED VERIFICATION, CAV 2018, PT II
Field
DocType
Volume
Binary logarithm,Discrete mathematics,Ackermann function,Computer science,Algorithm,DPLL algorithm,Proof complexity,Satisfiability modulo theories,Branching (version control),Exponential time hypothesis
Conference
10982
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
10
3
Name
Order
Citations
PageRank
Robert Robere1114.34
Antonina Kolokolova25010.09
Vijay Ganesh3156394.66