Back to search

University of Waterloo

Towards a Theoretical Understanding of the Power of Restart in SAT solvers

Abstract

dc:description.abstract

Restart policy is a widely used class of techniques integral to the efficiency of conflict-driven clause-learning (CDCL) SAT solvers. While the utility of such policies has been well-established, to-date we still lack a deep theoretical understanding of why restart policies are crucial to the power of CDCL SAT solvers. In this paper, we provide a series of results that theoretically establish the power of restarts for various models of Boolean SAT solvers. More precisely, we make the following contributions. First, we show that certain model of CDCL solvers with restarts are no more powerful from a proof-complexity theoretic point of view than the same configurations without restarts. Second, we define \textit{decision depth} for DPLL proofs of an unsatisfiable formula $\varphi$, and then we relate decision depth of $\varphi$ and size of DPLL proofs (or the running time of a DPLL based solver) for $\varphi$. Third, we introduce a new class of satisfiable instances called Laddern, then we use decision depth as a tool to proved that a drunk style DPLL solver with restarts can solve Laddern in polynomial time with high probability while the solvers with the same configuration without restarts have exponential run time with high probability. Finally, the crucial insight that drives this line of research is the fact that restarts add proof-theoretic or algorithmic power to solver configurations by compensating for the weaknesses of some other important heuristics like branching or value selection or clause learning.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Li, Chunxiao
Advisor dc:contributor.advisor
  • Ganesh, Vijay

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/15024

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Li, Chunxiao. Towards a Theoretical Understanding of the Power of Restart in SAT solvers. University of Waterloo, 2019. http://hdl.handle.net/10012/15024