Everything about SAT solver
Computer program for the Boolean satisfiability problem
In computer science and formal methods, a SAT solver is a computer program which aims to solve the Boolean satisfiability problem (SAT). On input a formula over Boolean variables, such as "(x or y) and (x or not y)", a SAT solver outputs whether the formula is satisfiable, meaning that there are possible values of x and y which make the formula true, or unsatisfiable, meaning that there are no such values of x and y. In this case, the formula is satisfiable when x is true, so the solver should return "satisfiable". Since the introduction of algorithms for SAT in the 1960s, modern SAT solvers have grown into complex software artifacts involving a large number of heuristics and program optimizations to work efficiently. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: SAT solverA 5-minute orientation
- Skim a recent paper: BONMIN solver-based coordination of distributed FACTS compensators and distributed generation units in modern distribution networksInfluential work since 2022
- Pick up a classic book: Mathematical logic for computer scienceThe most-reprinted book on the subject
- Read the landmark paper: ManySAT: a Parallel SAT SolverCited 160 times
- Go sideways: Boolean satisfiability problemA closely related topic
- Go sideways: DPLL algorithmA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
ManySAT: a Parallel SAT Solver
On the Glucose SAT Solver
Automated verification of access control policies using a SAT solver
MiniMaxSAT: An Efficient Weighted Max-SAT solver
A fast parallel SAT-solver — efficient workload balancing
BerkMin: A fast and robust Sat-solver
The International SAT Solver Competitions
QMaxSAT: A Partial Max-SAT Solver
🆕 Influential since 2022
BONMIN solver-based coordination of distributed FACTS compensators and distributed generation units in modern distribution networks
PRESTO: A Processing-in-Memory-Based k-SAT Solver Using Recurrent Stochastic Neural Network With Unsupervised Learning
SKADI: A 28-nm Complete K-SAT Solver Featuring Bidirectional In-Memory Deduction and Incremental Updating
An efficient circuit-based SAT solver and its application in logic equivalence checking
Graph neural network based time estimator for SAT solver
📚 Books worth reading
Mathematical logic for computer scienceM. Ben-Ari · 1993
Logic in Computer ScienceMark Ryan · 1999
Hardware and Software: Verification and TestingKerstin Eder · 2012
Tools and Algorithms for the Construction and Analysis of SystemsNir Piterman · 2013- 📕Efficient Implementation of Parallel SAT Solver Based Stochastic Local SearchSa'Ed Abed · 2020
- 📕First ACM and IEEE International Conference on Formal Methods and Models for Co-DesignFrance) ACM and IEEE International Conference on Formal Methods and Models for Co-Design (1st 2003 Le Mont-Saint-Michel · 2003
Automated Deduction – CADE-24Maria Paola Bonacina · 2013
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY…
- DPLL algorithm In logic and computer science, the Davis–Putnam–Logemann–Loveland (DPLL) algorithm is a complete, backtracking-based search algorithm for deciding the…
- Maximum satisfiability problem In computational complexity theory, the maximum satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given…
- Unsatisfiable core In mathematical logic, given an unsatisfiable Boolean propositional formula in conjunctive normal form, a subset of clauses whose conjunction is still…
- Satplan Satplan (better known as Planning as Satisfiability) is a method for automated planning. It converts the planning problem instance into an instance of…
- Satisfiability modulo theories In computer science and mathematical logic, satisfiability modulo theories (SMT) is the problem of determining whether a mathematical formula is satisfiable…
- Conflict-driven clause learning In computer science, conflict-driven clause learning (CDCL) is an algorithm for solving the Boolean satisfiability problem (SAT). Given a Boolean formula…
- 2-satisfiability In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values…