2275:
459:
the ideal form for a conflict-driven solver. Furthermore, look-ahead solvers consider the entire problem whereas conflict-driven solvers make decisions based on information that is much more local. There are three heuristics involved in the cube phase. The variables in the cubes are chosen by the decision heuristic. The direction heuristic decides which variable assignment (true or false) to explore first. In satisfiable problem instances, choosing a satisfiable branch first is beneficial. The cutoff heuristic decides when to stop expanding a cube and instead forward it to a sequential conflict-driven solver. Preferably the cubes are similarly complex to solve.
378:
will solve this instance particularly fast. These limitations motivate the parallel portfolio approach. A portfolio is a set of different algorithms or different configurations of the same algorithm. All solvers in a parallel portfolio run on different processors to solve of the same problem. If one solver terminates, the portfolio solver reports the problem to be satisfiable or unsatisfiable according to this one solver. All other solvers are terminated. Diversifying portfolios by including a variety of solvers, each performing well on a different set of problems, increases the robustness of the solver.
393:
makes a competitive parallel solver. An example of such a solver is PPfolio. It was designed to find a lower bound for the performance a parallel SAT solver should be able to deliver. Despite the large amount of duplicate work due to lack of optimizations, it performed well on a shared memory machine. HordeSat is a parallel portfolio solver for large clusters of computing nodes. It uses differently configured instances of the same sequential solver at its core. Particularly for hard SAT instances HordeSat can produce linear speedups and therefore reduce runtime significantly.
413:
2829:
2849:
2839:
261:("DPLL" or "DLL"). Many modern approaches to practical SAT solving are derived from the DPLL algorithm and share the same structure. Often they only improve the efficiency of certain classes of SAT problems such as instances that appear in industrial applications or randomly generated instances. Theoretically, exponential lower bounds have been proved for the DPLL family of algorithms.
122:, but incorporate a number of extensions and features. Most SAT solvers include time-outs, so they will terminate in reasonable time even if they cannot find a solution with an output such as "unknown". Often, SAT solvers do not just provide an answer, but can provide further information including an example assignment (values for
404:
In contrast to parallel portfolios, parallel divide-and-conquer tries to split the search space between the processing elements. Divide-and-conquer algorithms, such as the sequential DPLL, already apply the technique of splitting the search space, hence their extension towards a parallel algorithm is
377:
In general there is no SAT solver that performs better than all other solvers on all SAT problems. An algorithm might perform well for problem instances others struggle with, but will do worse with other instances. Furthermore, given a SAT instance, there is no reliable way to predict which algorithm
306:
The conflict-driven MiniSAT, which was relatively successful at the 2005 SAT competition, only has about 600 lines of code. A modern
Parallel SAT solver is ManySAT. It can achieve super linear speed-ups on important classes of problems. An example for look-ahead solvers is march_dl, which won a prize
110:
problem in general. As a result, only algorithms with exponential worst-case complexity are known. In spite of this, efficient and scalable algorithms for SAT were developed during the 2000s, which have contributed to dramatic advances in the ability to automatically solve problem instances involving
392:
One drawback of parallel portfolios is the amount of duplicate work. If clause learning is used in the sequential solvers, sharing learned clauses between parallel running solvers can reduce duplicate work and increase performance. Yet, even merely running a portfolio of the best solvers in parallel
458:
to the original formula, the problem is reported to be satisfiable, if one of the formulas is satisfiable. The look-ahead solver is favorable for small but hard problems, so it is used to gradually divide the problem into multiple sub-problems. These sub-problems are easier but still large which is
482:
One strategy towards a parallel local search algorithm for SAT solving is trying multiple variable flips concurrently on different processing units. Another is to apply the aforementioned portfolio approach, however clause sharing is not possible since local search solvers do not produce clauses.
256:
A DPLL SAT solver employs a systematic backtracking search procedure to explore the (exponentially sized) space of variable assignments looking for satisfying assignments. The basic search procedure was proposed in two seminal papers in the early 1960s (see references below) and is now commonly
302:
Look-ahead solvers have especially strengthened reductions (going beyond unit-clause propagation) and the heuristics, and they are generally stronger than conflict-driven solvers on hard instances (while conflict-driven solvers can be much better on large instances which actually have an easy
405:
straight forward. However, due to techniques like unit propagation, following a division, the partial problems may differ significantly in complexity. Thus the DPLL algorithm typically does not process each part of the search space in the same amount of time, yielding a challenging
349:
algorithms. With parallel portfolios, multiple different SAT solvers run concurrently. Each of them solves a copy of the SAT instance, whereas divide-and-conquer algorithms divide the problem between the processors. Different approaches exist to parallelize local search algorithms.
444:
paradigm. It suggests solving in two phases. In the "cube" phase the
Problem is divided into many thousands, up to millions, of sections. This is done by a look-ahead solver, that finds a set of partial configurations called "cubes". A cube can also be seen as a
462:
Treengeling is an example for a parallel solver that applies the Cube-and-Conquer paradigm. Since its introduction in 2012 it has had multiple successes at the
International SAT Solver Competition. Cube-and-Conquer was used to solve the
483:
Alternatively, it is possible to share the configurations that are produced locally. These configurations can be used to guide the production of a new initial configuration when a local solver decides to restart its search.
449:
of a subset of variables of the original formula. In conjunction with the formula, each of the cubes forms a new formula. These formulas can be solved independently and concurrently by conflict-driven solvers. As the
329:
Different SAT solvers will find different instances easy or hard, and some excel at proving unsatisfiability, and others at finding solutions. All of these behaviors can be seen in the SAT solving contests.
704:
and other classic impossibility theorems. Geist and
Endriss used it to find new impossibilities related to set extensions. Brandt and Geist used this approach to prove an impossibility about strategyproof
436:. The decision heuristic chooses which variables (circles) to assign. After the cutoff heuristic decides to stop further branching, the partial problems (rectangles) are solved independently using CDCL.
396:
In recent years parallel portfolio SAT solvers have dominated the parallel track of the
International SAT Solver Competitions. Notable examples of such solvers include Plingeling and painless-mcomsps.
585:
for 3-SAT. The latter is currently the fastest known algorithm for k-SAT at all values of k. In the setting with many satisfying assignments the randomized algorithm by Schöning has a better bound.
287:, adaptive branching, and random restarts. These "extras" to the basic systematic search have been empirically shown to be essential for handling the large SAT instances that arise in
505:
In contrast, randomized algorithms like the PPSZ algorithm by Paturi, Pudlak, Saks, and Zane set variables in a random order according to some heuristics, for example bounded-width
2189:
2852:
2842:
583:
549:
for 3-SAT. This was the best-known runtime for this problem until 2019, when Hansen, Kaplan, Zamir and Zwick published a modification of that algorithm with a runtime of
547:
1710:
275:
Modern SAT solvers (developed in the 2000s) come in two flavors: "conflict-driven" and "look-ahead". Both approaches descend from DPLL. Conflict-driven solvers, such as
353:
The
International SAT Solver Competition has a parallel track reflecting recent advances in parallel SAT solving. In 2016, 2017 and 2018, the benchmarks were run on a
502:. Stochastic methods try to find a satisfying interpretation but cannot deduce that a SAT instance is unsatisfiable, as opposed to complete algorithms, such as DPLL.
2414:
389:
is a simple way to diversify a portfolio. Other diversification strategies involve enabling, disabling or diversifying certain heuristics in the sequential solver.
434:
322:
applications, satisfiability and other logical properties of a given propositional formula are sometimes decided based on a representation of the formula as a
2612:
2511:
258:
650:(in particular, bounded model checking), SAT solvers are used to check whether a finite-state system satisfies a specification of its intended behavior.
441:
1783:
Heule, Marijn J. H.; Kullmann, Oliver; Marek, Victor W. (2016), "Solving and
Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer",
2494:
1067:
440:
Due to non-chronological backtracking, parallelization of conflict-driven clause learning is more difficult. One way to overcome this is the
2196:
1970:
1472:; Kullmann, Oliver; Marek, Victor W. (2016), "Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer",
622:
by using a SAT solver to show that there is no way to color the integers up to 7825 in the required fashion. Small values of the
495:
474:
w(2;3,17) and w(2;3,18) in 2010 where both the phases (splitting and solving the partial problems) were performed using DPLL.
346:
2141:
1810:
1614:
1582:
1499:
1453:
1419:
1349:
1237:
994:
922:
787:
937:
Vizel, Y.; Weissenbacher, G.; Malik, S. (2015). "Boolean
Satisfiability Solvers and Their Applications in Model Checking".
717:. Brandl, Brandt, Peters and Stricker used it to prove the impossibility of a strategyproof, efficient and fair rule for
619:
470:
Cube-and-Conquer is a modification or a generalization of the DPLL-based Divide-and-conquer approach used to compute the
464:
291:(EDA). Most state-of-the-art SAT solvers are based on the CDCL framework as of 2019. Well known implementations include
2878:
1402:; Kullmann, Oliver; Wieringa, Siert; Biere, Armin (2012), "Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads",
2451:
1997:
1661:
314:
Certain types of large random satisfiable instances of SAT can be solved by survey propagation (SP). Particularly in
130:, etc.) in case the formula is satisfiable or minimal set of unsatisfiable clauses if the formula is unsatisfiable.
2883:
701:
2550:
276:
270:
142:
794:
modern SAT solvers can often handle problems with millions of constraints and hundreds of thousands of variables
238:
which asks, on input a
Boolean formula, to determine whether the formula is satisfiable or not. This problem is
2711:
2565:
2259:
2224:
1042:
740:
654:
509:. If the heuristic can't find the correct setting, the variable is assigned randomly. The PPSZ algorithm has a
174:
36:
2801:
2274:
158:
2764:
2283:
2234:
1322:
Balyo, Tomáš; Sanders, Peter; Sinz, Carsten (2015), "HordeSat: A Massively
Parallel Portfolio SAT Solver",
1253:
841:
342:
288:
162:
150:
2703:
1476:, Lecture Notes in Computer Science, vol. 9710, Springer International Publishing, pp. 228–245,
1326:, Lecture Notes in Computer Science, vol. 9340, Springer International Publishing, pp. 156–172,
2739:
2658:
714:
2769:
2489:
1169:
1145:
406:
2061:
2832:
2360:
2182:
853:
700:, SAT solvers have been used to prove impossibility theorems. Tang and Lin used SAT solvers to prove
311:, won gold medals at the Minizinc constraint programming competitions in 2018, 2019, 2020, and 2021.
760:
Ohrimenko, Olga; Stuckey, Peter J.; Codish, Michael (2007), "Propagation = Lazy Clause Generation",
2683:
2481:
1569:, Lecture Notes in Computer Science, vol. 2470, Springer Berlin Heidelberg, pp. 714–719,
1298:
1090:
770:
718:
382:
279:(CDCL), augment the basic DPLL search algorithm with efficient conflict analysis, clause learning,
552:
516:
2873:
2643:
2399:
2391:
1601:, Lecture Notes in Computer Science, vol. 6683, Springer Berlin Heidelberg, pp. 46–60,
1406:, Lecture Notes in Computer Science, vol. 7261, Springer Berlin Heidelberg, pp. 50–65,
907:, Lecture Notes in Computer Science, vol. 2404, Springer Berlin Heidelberg, pp. 17–36,
735:
599:
358:
323:
146:
115:
1438:
2786:
2781:
2584:
2303:
903:
Zhang, Lintao; Malik, Sharad (2002), "The Quest for Efficient Boolean Satisfiability Solvers",
765:
674:
607:
471:
103:
2409:
2315:
2308:
1019:
643:
639:
319:
161:
and are built into some programming languages such as exposing SAT solvers as constraints in
134:
1969:
Biere, Armin; Cimatti, Alessandro; Clarke, Edmund M.; Strichman, Ofer; Zhu, Yunshan (2003).
2579:
2574:
2461:
2337:
2325:
2254:
1846:
1769:
1543:
1193:
730:
697:
96:
2099:
Peters, Dominik (2021). "Proportionality and Strategyproofness in Multiwinner Elections".
8:
2591:
2426:
2298:
706:
690:
635:
455:
451:
446:
366:
215:
consists of choosing, for each variable, an assignment TRUE or FALSE. For any assignment
154:
1850:
1597:
Arbelaez, Alejandro; Hamadi, Youssef (2011), "Improving Parallel Local Search for SAT",
71:
which make the formula true, or unsatisfiable, meaning that there are no such values of
2560:
2501:
2471:
2456:
2421:
2320:
2264:
2219:
2147:
2100:
2042:
1951:
1880:
1816:
1788:
1738:
1667:
1620:
1547:
1505:
1477:
1355:
1327:
1048:
1000:
954:
880:
823:
662:
623:
506:
419:
362:
338:
296:
219:, the Boolean formula can be evaluated, and evaluates to true or false. The formula is
1989:
1113:
2675:
2249:
2151:
2137:
2081:
2034:
1993:
1943:
1872:
1864:
1806:
1730:
1671:
1657:
1610:
1578:
1551:
1495:
1449:
1415:
1345:
1233:
1038:
1004:
990:
918:
783:
678:
40:
2128:. EC '21. New York, NY, USA: Association for Computing Machinery. pp. 158–179.
2046:
1834:
1624:
1359:
958:
884:
827:
2622:
2521:
2446:
2355:
2205:
2129:
2120:
Brandl, Florian; Brandt, Felix; Peters, Dominik; Stricker, Christian (2021-07-18).
2073:
2026:
1985:
1955:
1935:
1884:
1854:
1820:
1798:
1742:
1726:
1722:
1649:
1602:
1570:
1531:
1509:
1487:
1407:
1337:
1274:
1225:
1082:
1052:
1030:
982:
946:
908:
875:
870:
862:
815:
775:
284:
235:
138:
32:
20:
1638:
2726:
2516:
2436:
2345:
1802:
1765:
1539:
1522:
Ahmed, Tanbir (2010). "Two new van der Waerden numbers w(2;3,17) and w(2;3,18)".
1491:
1341:
986:
973:
806:
Davis, M.; Putnam, H. (1960). "A Computing Procedure for Quantification Theory".
779:
710:
315:
292:
239:
107:
2062:"Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers"
1606:
1565:
Roli, Andrea (2002), "Criticality and Parallelism in Structured SAT Instances",
1411:
1229:
2744:
2627:
2555:
2535:
2441:
2404:
2370:
2239:
2077:
950:
845:
693:, SAT solvers have been applied to solve optimization and scheduling problems.
666:
647:
251:
119:
60:
24:
2122:"Distribution Rules Under Dichotomous Preferences: Two Out of Three Ain't Bad"
1939:
1859:
1653:
598:
SAT solvers have been used to assist in proving mathematical theorems through
183:
is any expression that can be written using Boolean (propositional) variables
83:
is true, so the solver should return "satisfiable". Since the introduction of
2867:
2431:
2365:
2229:
2085:
2038:
1947:
1868:
1734:
1574:
658:
603:
354:
2133:
2030:
1696:
1684:
1646:
40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)
913:
709:. Other authors used this technology to prove new impossibilities about the
2791:
2774:
2617:
2244:
1898:
1876:
1535:
1469:
1434:
1399:
615:
412:
2121:
2014:
1923:
1756:
Kouril, Michal (2012). "Computing the van der Waerden number W(3,4)=293".
1639:"A probabilistic algorithm for k-SAT and constraint satisfaction problems"
1034:
866:
819:
2607:
2466:
1922:
Clarke, Edmund; Biere, Armin; Raimi, Richard; Zhu, Yunshan (2001-07-01).
1018:
Moskewicz, M. W.; Madigan, C. F.; Zhao, Y.; Zhang, L.; Malik, S. (2001).
670:
386:
280:
981:. Lecture Notes in Computer Science. Vol. 11628. pp. 250–266.
2693:
1787:, Lecture Notes in Computer Science, vol. 9710, pp. 228–245,
1372:
764:, Lecture Notes in Computer Science, vol. 4741, pp. 544–558,
673:, and other applications. These techniques are also closely related to
492:
1086:
2754:
2570:
2350:
133:
Modern SAT solvers have had a significant impact on fields including
92:
84:
2653:
2174:
2126:
Proceedings of the 22nd ACM Conference on Economics and Computation
2105:
1793:
1482:
1332:
308:
88:
610:
were computed with the help of specialized SAT solvers running on
2648:
2506:
1125:
499:
87:
for SAT in the 1960s, modern SAT solvers have grown into complex
2168:
2015:"Satisfiability modulo theories: introduction and applications"
1220:
Balyo, Tomáš; Sinz, Carsten (2018), "Parallel Satisfiability",
1254:"Lingeling, Plingeling, PicoSAT and PrecoSAT at SAT Race 2010"
2806:
2796:
2716:
1324:
Theory and Applications of Satisfiability Testing -- SAT 2015
1027:
Proceedings of the 38th conference on Design automation (DAC)
972:
Möhle, Sibylle; Biere, Armin (2019). "Backing Backtracking".
657:(SMT) solvers are built, which are used for problems such as
307:
at the 2007 SAT competition. Google's CP-SAT solver, part of
1785:
Theory and Applications of Satisfiability Testing – SAT 2016
1474:
Theory and Applications of Satisfiability Testing – SAT 2016
1068:"GRASP: a search algorithm for propositional satisfiability"
975:
Theory and Applications of Satisfiability Testing – SAT 2019
753:
111:
tens of thousands of variables and millions of constraints.
2759:
2734:
1968:
1567:
Principles and Practice of Constraint Programming - CP 2002
762:
Principles and Practice of Constraint Programming – CP 2007
611:
2119:
1398:
1299:"SAT 2011 Competition: 32 cores track: ranking of solvers"
187:
and the Boolean operations AND, OR, and NOT. For example,
1017:
491:
Algorithms that are not part of the DPLL family include
2749:
936:
16:
Computer program for the Boolean satisfiability problem
759:
118:. They are often based on core algorithms such as the
1924:"Bounded Model Checking Using Satisfiability Solving"
1690:
1065:
840:
555:
519:
422:
1224:, Springer International Publishing, pp. 3–29,
2013:De Moura, Leonardo; Bjørner, Nikolaj (2011-09-01).
1921:
1114:
http://www.cril.univ-artois.fr/~jabbour/manysat.htm
114:SAT solvers often begin by converting a formula to
1835:"Two-hundred-terabyte maths proof is largest ever"
1782:
1685:"An improved exponential-time algorithm for k-SAT"
1468:
577:
541:
428:
341:SAT solvers come in three categories: portfolio,
2865:
1321:
79:. In this case, the formula is satisfiable when
59:)", a SAT solver outputs whether the formula is
2059:
2012:
1711:"The van der Waerden Number $ W(2,6)$ Is 1132"
1433:
1404:Hardware and Software: Verification and Testing
626:were also computed by Heule using SAT solvers.
618:, Oliver Kullmann, and Victor Marek solved the
1678:
1596:
1066:Marques-Silva, J. P.; Sakallah, K. A. (1999).
2190:
2060:Coelho, José; Vanhoucke, Mario (2011-08-16).
1630:
1126:"The international SAT Competitions web page"
1020:"Chaff: Engineering an Efficient SAT Solver"
653:SAT solvers are the core component on which
157:. Powerful solvers are readily available as
63:, meaning that there are possible values of
1697:"Faster k-SAT algorithms using biased-PPSZ"
805:
629:
227:) for which the formula evaluates to true.
2848:
2838:
2197:
2183:
1749:
1708:
971:
902:
2104:
1858:
1792:
1481:
1331:
1222:Handbook of Parallel Constraint Reasoning
1219:
912:
874:
769:
2066:European Journal of Operational Research
1709:Kouril, Michal; Paul, Jerome L. (2008).
1636:
486:
411:
259:Davis–Putnam–Logemann–Loveland algorithm
223:if there exists an assignment (called a
846:"A machine program for theorem-proving"
333:
2866:
2098:
1755:
2178:
1599:Learning and Intelligent Optimization
1521:
1394:
1392:
1215:
1213:
844:; Logemann, G.; Loveland, D. (1962).
399:
2204:
1832:
1564:
898:
896:
894:
620:Boolean Pythagorean triples problem
465:Boolean Pythagorean triples problem
283:, a "two-watched-literals" form of
13:
1462:
1389:
1210:
14:
2895:
2162:
1251:
891:
684:
593:
361:, therefore solvers intended for
2847:
2837:
2828:
2827:
2273:
669:, program verification based on
2113:
2092:
2053:
2006:
1962:
1928:Formal Methods in System Design
1915:
1891:
1826:
1776:
1702:
1590:
1558:
1515:
1448:. IOS Press. pp. 155–184.
1427:
1365:
1315:
1291:
1267:
1245:
1186:
1162:
1138:
1118:
588:
477:
277:conflict-driven clause learning
271:Conflict-driven clause learning
264:
245:
106:, Boolean satisfiability is an
2171:of Sat competitions since 2002
1727:10.1080/10586458.2008.10129025
1699:, Hansen, Kaplan, Zamir, Zwick
1439:"Look-Ahead Based SAT Solvers"
1107:
1075:IEEE Transactions on Computers
1059:
1011:
965:
930:
834:
799:
741:Satisfiability modulo theories
655:satisfiability modulo theories
572:
559:
536:
523:
381:Many solvers internally use a
232:Boolean satisfiability problem
175:Boolean satisfiability problem
37:Boolean satisfiability problem
1:
1990:10.1016/S0065-2458(03)58003-2
746:
713:, half-way monotonicity, and
606:, several previously unknown
372:
159:free and open-source software
1803:10.1007/978-3-319-40970-2_15
1687:, Paturi, Pudlak, Saks, Zani
1492:10.1007/978-3-319-40970-2_15
1377:sat2018.forsyte.tuwien.ac.at
1342:10.1007/978-3-319-24318-4_12
1198:sat2018.forsyte.tuwien.ac.at
987:10.1007/978-3-030-24258-9_18
780:10.1007/978-3-540-74970-7_39
578:{\displaystyle O(1.307^{n})}
542:{\displaystyle O(1.308^{n})}
289:electronic design automation
163:constraint logic programming
151:electronic design automation
91:involving a large number of
7:
2551:Curry–Howard correspondence
2002:– via Academic Press.
1833:Lamb, Evelyn (2016-06-01).
1607:10.1007/978-3-642-25566-3_4
1437:; van Maaren, Hans (2009).
1412:10.1007/978-3-642-34188-5_8
1230:10.1007/978-3-319-63516-3_1
905:Computer Aided Verification
724:
498:algorithms. One example is
416:Cube phase for the formula
168:
10:
2900:
2078:10.1016/j.ejor.2011.03.019
1637:Schöning, Uwe (Oct 1999).
1446:Handbook of Satisfiability
951:10.1109/JPROC.2015.2455034
715:probabilistic voting rules
268:
249:
172:
39:. On input a formula over
2879:Logic in computer science
2823:
2725:
2702:
2674:
2667:
2636:
2600:
2543:
2534:
2480:
2390:
2383:
2336:
2291:
2282:
2271:
2212:
2019:Communications of the ACM
1860:10.1038/nature.2016.19990
1654:10.1109/SFFCS.1999.814612
854:Communications of the ACM
369:might have fallen short.
102:By a result known as the
1971:"Bounded Model Checking"
1715:Experimental Mathematics
1575:10.1007/3-540-46135-3_51
719:fractional social choice
634:SAT solvers are used in
630:In software verification
35:which aims to solve the
2884:Satisfiability problems
2400:Abstract interpretation
2134:10.1145/3465456.3467653
2031:10.1145/1995376.1995394
1940:10.1023/A:1011276507260
1303:www.cril.univ-artois.fr
1279:www.cril.univ-artois.fr
939:Proceedings of the IEEE
914:10.1007/3-540-45657-0_2
876:2027/mdp.39015095248095
736:Computer-assisted proof
608:Van der Waerden numbers
600:computer-assisted proof
472:Van der Waerden numbers
383:random number generator
324:binary decision diagram
147:artificial intelligence
116:conjunctive normal form
1536:10.1515/integ.2010.032
1373:"SAT Competition 2018"
1194:"SAT Competition 2018"
1170:"SAT Competition 2017"
1146:"SAT Competition 2016"
675:constraint programming
579:
543:
437:
430:
2309:Categorical semantics
1978:Advances in Computers
1035:10.1145/378239.379017
867:10.1145/368273.368557
820:10.1145/321033.321034
580:
544:
487:Randomized approaches
454:of these formulas is
431:
415:
385:. Diversifying their
225:satisfying assignment
135:software verification
99:to work efficiently.
97:program optimizations
43:variables, such as "(
2255:Runtime verification
1648:. pp. 410–414.
731:Category:SAT solvers
707:tournament solutions
698:social choice theory
553:
517:
420:
334:Parallel SAT-solving
2512:Invariant inference
2260:Safety and liveness
1899:"Schur Number Five"
1851:2016Natur.534...17L
1470:Heule, Marijn J. H.
1435:Heule, Marijn J. H.
1400:Heule, Marijn J. H.
691:operations research
636:formal verification
367:manycore processors
257:referred to as the
155:operations research
2676:Constraint solvers
2502:Concolic execution
2457:Symbolic execution
2265:Undefined behavior
2220:Control-flow graph
1174:baldur.iti.kit.edu
1150:baldur.iti.kit.edu
808:Journal of the ACM
663:symbolic execution
575:
539:
438:
426:
400:Divide-and-conquer
363:distributed memory
343:divide-and-conquer
303:instance inside).
143:constraint solving
104:Cook–Levin theorem
89:software artifacts
2861:
2860:
2819:
2818:
2815:
2814:
2530:
2529:
2379:
2378:
2143:978-1-4503-8554-1
1984:(2003): 117–148.
1903:www.cs.utexas.edu
1812:978-3-319-40969-6
1616:978-3-642-25565-6
1584:978-3-540-44120-5
1501:978-3-319-40969-6
1455:978-1-58603-929-5
1421:978-3-642-34187-8
1351:978-3-319-24317-7
1239:978-3-319-63515-6
1087:10.1109/12.769433
996:978-3-030-24257-2
945:(11): 2021–2035.
924:978-3-540-43997-4
789:978-3-540-74969-1
679:logic programming
429:{\displaystyle F}
2891:
2851:
2850:
2841:
2840:
2831:
2830:
2727:Proof assistants
2672:
2671:
2541:
2540:
2388:
2387:
2361:Rewriting system
2356:Process calculus
2289:
2288:
2277:
2206:Program analysis
2199:
2192:
2185:
2176:
2175:
2156:
2155:
2117:
2111:
2110:
2108:
2096:
2090:
2089:
2057:
2051:
2050:
2010:
2004:
2003:
1975:
1966:
1960:
1959:
1919:
1913:
1912:
1910:
1909:
1895:
1889:
1888:
1862:
1830:
1824:
1823:
1796:
1780:
1774:
1773:
1753:
1747:
1746:
1706:
1700:
1694:
1688:
1682:
1676:
1675:
1643:
1634:
1628:
1627:
1594:
1588:
1587:
1562:
1556:
1555:
1519:
1513:
1512:
1485:
1466:
1460:
1459:
1443:
1431:
1425:
1424:
1396:
1387:
1386:
1384:
1383:
1369:
1363:
1362:
1335:
1319:
1313:
1312:
1310:
1309:
1295:
1289:
1288:
1286:
1285:
1275:"ppfolio solver"
1271:
1265:
1264:
1258:
1249:
1243:
1242:
1217:
1208:
1207:
1205:
1204:
1190:
1184:
1183:
1181:
1180:
1166:
1160:
1159:
1157:
1156:
1142:
1136:
1135:
1133:
1132:
1122:
1116:
1111:
1105:
1104:
1102:
1101:
1095:
1089:. Archived from
1072:
1063:
1057:
1056:
1024:
1015:
1009:
1008:
980:
969:
963:
962:
934:
928:
927:
916:
900:
889:
888:
878:
850:
838:
832:
831:
803:
797:
796:
773:
757:
584:
582:
581:
576:
571:
570:
548:
546:
545:
540:
535:
534:
512:
442:Cube-and-Conquer
435:
433:
432:
427:
359:processing cores
285:unit propagation
236:decision problem
139:program analysis
33:computer program
21:computer science
2899:
2898:
2894:
2893:
2892:
2890:
2889:
2888:
2864:
2863:
2862:
2857:
2811:
2721:
2698:
2663:
2637:Data structures
2632:
2596:
2526:
2517:Program slicing
2476:
2375:
2346:Lambda calculus
2332:
2278:
2269:
2230:Hyperproperties
2208:
2203:
2165:
2160:
2159:
2144:
2118:
2114:
2097:
2093:
2058:
2054:
2011:
2007:
2000:
1973:
1967:
1963:
1920:
1916:
1907:
1905:
1897:
1896:
1892:
1845:(7605): 17–18.
1831:
1827:
1813:
1781:
1777:
1754:
1750:
1707:
1703:
1695:
1691:
1683:
1679:
1664:
1641:
1635:
1631:
1617:
1595:
1591:
1585:
1563:
1559:
1520:
1516:
1502:
1467:
1463:
1456:
1441:
1432:
1428:
1422:
1397:
1390:
1381:
1379:
1371:
1370:
1366:
1352:
1320:
1316:
1307:
1305:
1297:
1296:
1292:
1283:
1281:
1273:
1272:
1268:
1256:
1250:
1246:
1240:
1218:
1211:
1202:
1200:
1192:
1191:
1187:
1178:
1176:
1168:
1167:
1163:
1154:
1152:
1144:
1143:
1139:
1130:
1128:
1124:
1123:
1119:
1112:
1108:
1099:
1097:
1093:
1070:
1064:
1060:
1045:
1029:. p. 530.
1022:
1016:
1012:
997:
978:
970:
966:
935:
931:
925:
901:
892:
848:
839:
835:
804:
800:
790:
758:
754:
749:
727:
711:no-show paradox
702:Arrow's theorem
687:
632:
596:
591:
566:
562:
554:
551:
550:
530:
526:
518:
515:
514:
510:
489:
480:
421:
418:
417:
402:
375:
357:system with 24
336:
316:hardware design
273:
267:
254:
248:
181:Boolean formula
177:
171:
17:
12:
11:
5:
2897:
2887:
2886:
2881:
2876:
2874:Formal methods
2859:
2858:
2856:
2855:
2845:
2835:
2824:
2821:
2820:
2817:
2816:
2813:
2812:
2810:
2809:
2804:
2799:
2794:
2789:
2784:
2779:
2778:
2777:
2767:
2762:
2757:
2752:
2747:
2742:
2737:
2731:
2729:
2723:
2722:
2720:
2719:
2714:
2708:
2706:
2700:
2699:
2697:
2696:
2691:
2686:
2680:
2678:
2669:
2665:
2664:
2662:
2661:
2656:
2651:
2646:
2640:
2638:
2634:
2633:
2631:
2630:
2625:
2620:
2615:
2610:
2604:
2602:
2598:
2597:
2595:
2594:
2589:
2588:
2587:
2577:
2568:
2563:
2558:
2556:Loop invariant
2553:
2547:
2545:
2538:
2536:Formal methods
2532:
2531:
2528:
2527:
2525:
2524:
2519:
2514:
2509:
2504:
2499:
2498:
2497:
2495:Taint tracking
2486:
2484:
2478:
2477:
2475:
2474:
2469:
2464:
2459:
2454:
2449:
2444:
2442:Model checking
2439:
2434:
2429:
2424:
2419:
2418:
2417:
2407:
2402:
2396:
2394:
2385:
2381:
2380:
2377:
2376:
2374:
2373:
2371:Turing machine
2368:
2363:
2358:
2353:
2348:
2342:
2340:
2334:
2333:
2331:
2330:
2329:
2328:
2323:
2313:
2312:
2311:
2301:
2295:
2293:
2286:
2280:
2279:
2272:
2270:
2268:
2267:
2262:
2257:
2252:
2250:Rice's theorem
2247:
2242:
2240:Path explosion
2237:
2232:
2227:
2222:
2216:
2214:
2210:
2209:
2202:
2201:
2194:
2187:
2179:
2173:
2172:
2164:
2163:External links
2161:
2158:
2157:
2142:
2112:
2091:
2052:
2005:
1998:
1961:
1914:
1890:
1825:
1811:
1775:
1748:
1701:
1689:
1677:
1662:
1629:
1615:
1589:
1583:
1557:
1530:(4): 369–377.
1514:
1500:
1461:
1454:
1426:
1420:
1388:
1364:
1350:
1314:
1290:
1266:
1252:Biere, Armin.
1244:
1238:
1209:
1185:
1161:
1137:
1117:
1106:
1058:
1043:
1010:
995:
964:
929:
923:
890:
861:(7): 394–397.
833:
798:
788:
771:10.1.1.70.5471
751:
750:
748:
745:
744:
743:
738:
733:
726:
723:
686:
685:In other areas
683:
667:model checking
659:job scheduling
648:model checking
631:
628:
595:
594:In mathematics
592:
590:
587:
574:
569:
565:
561:
558:
538:
533:
529:
525:
522:
488:
485:
479:
476:
425:
407:load balancing
401:
398:
374:
371:
335:
332:
269:Main article:
266:
263:
252:DPLL algorithm
250:Main article:
247:
244:
209:
208:
173:Main article:
170:
167:
120:DPLL algorithm
25:formal methods
15:
9:
6:
4:
3:
2:
2896:
2885:
2882:
2880:
2877:
2875:
2872:
2871:
2869:
2854:
2846:
2844:
2836:
2834:
2826:
2825:
2822:
2808:
2805:
2803:
2800:
2798:
2795:
2793:
2790:
2788:
2785:
2783:
2780:
2776:
2773:
2772:
2771:
2768:
2766:
2763:
2761:
2758:
2756:
2753:
2751:
2748:
2746:
2743:
2741:
2738:
2736:
2733:
2732:
2730:
2728:
2724:
2718:
2715:
2713:
2710:
2709:
2707:
2705:
2701:
2695:
2692:
2690:
2687:
2685:
2682:
2681:
2679:
2677:
2673:
2670:
2666:
2660:
2657:
2655:
2652:
2650:
2647:
2645:
2642:
2641:
2639:
2635:
2629:
2626:
2624:
2621:
2619:
2616:
2614:
2613:Incorrectness
2611:
2609:
2606:
2605:
2603:
2599:
2593:
2590:
2586:
2583:
2582:
2581:
2580:Specification
2578:
2576:
2572:
2569:
2567:
2564:
2562:
2559:
2557:
2554:
2552:
2549:
2548:
2546:
2542:
2539:
2537:
2533:
2523:
2520:
2518:
2515:
2513:
2510:
2508:
2505:
2503:
2500:
2496:
2493:
2492:
2491:
2488:
2487:
2485:
2483:
2479:
2473:
2470:
2468:
2465:
2463:
2460:
2458:
2455:
2453:
2450:
2448:
2445:
2443:
2440:
2438:
2435:
2433:
2432:Effect system
2430:
2428:
2425:
2423:
2420:
2416:
2413:
2412:
2411:
2408:
2406:
2403:
2401:
2398:
2397:
2395:
2393:
2389:
2386:
2382:
2372:
2369:
2367:
2366:State machine
2364:
2362:
2359:
2357:
2354:
2352:
2349:
2347:
2344:
2343:
2341:
2339:
2335:
2327:
2324:
2322:
2319:
2318:
2317:
2314:
2310:
2307:
2306:
2305:
2302:
2300:
2297:
2296:
2294:
2290:
2287:
2285:
2281:
2276:
2266:
2263:
2261:
2258:
2256:
2253:
2251:
2248:
2246:
2243:
2241:
2238:
2236:
2233:
2231:
2228:
2226:
2223:
2221:
2218:
2217:
2215:
2211:
2207:
2200:
2195:
2193:
2188:
2186:
2181:
2180:
2177:
2170:
2167:
2166:
2153:
2149:
2145:
2139:
2135:
2131:
2127:
2123:
2116:
2107:
2102:
2095:
2087:
2083:
2079:
2075:
2071:
2067:
2063:
2056:
2048:
2044:
2040:
2036:
2032:
2028:
2024:
2020:
2016:
2009:
2001:
1999:9780120121588
1995:
1991:
1987:
1983:
1979:
1972:
1965:
1957:
1953:
1949:
1945:
1941:
1937:
1933:
1929:
1925:
1918:
1904:
1900:
1894:
1886:
1882:
1878:
1874:
1870:
1866:
1861:
1856:
1852:
1848:
1844:
1840:
1836:
1829:
1822:
1818:
1814:
1808:
1804:
1800:
1795:
1790:
1786:
1779:
1771:
1767:
1763:
1759:
1752:
1744:
1740:
1736:
1732:
1728:
1724:
1720:
1716:
1712:
1705:
1698:
1693:
1686:
1681:
1673:
1669:
1665:
1663:0-7695-0409-4
1659:
1655:
1651:
1647:
1640:
1633:
1626:
1622:
1618:
1612:
1608:
1604:
1600:
1593:
1586:
1580:
1576:
1572:
1568:
1561:
1553:
1549:
1545:
1541:
1537:
1533:
1529:
1525:
1518:
1511:
1507:
1503:
1497:
1493:
1489:
1484:
1479:
1475:
1471:
1465:
1457:
1451:
1447:
1440:
1436:
1430:
1423:
1417:
1413:
1409:
1405:
1401:
1395:
1393:
1378:
1374:
1368:
1361:
1357:
1353:
1347:
1343:
1339:
1334:
1329:
1325:
1318:
1304:
1300:
1294:
1280:
1276:
1270:
1262:
1261:SAT-RACE 2010
1255:
1248:
1241:
1235:
1231:
1227:
1223:
1216:
1214:
1199:
1195:
1189:
1175:
1171:
1165:
1151:
1147:
1141:
1127:
1121:
1115:
1110:
1096:on 2016-11-04
1092:
1088:
1084:
1080:
1076:
1069:
1062:
1054:
1050:
1046:
1040:
1036:
1032:
1028:
1021:
1014:
1006:
1002:
998:
992:
988:
984:
977:
976:
968:
960:
956:
952:
948:
944:
940:
933:
926:
920:
915:
910:
906:
899:
897:
895:
886:
882:
877:
872:
868:
864:
860:
856:
855:
847:
843:
837:
829:
825:
821:
817:
813:
809:
802:
795:
791:
785:
781:
777:
772:
767:
763:
756:
752:
742:
739:
737:
734:
732:
729:
728:
722:
720:
716:
712:
708:
703:
699:
694:
692:
682:
680:
676:
672:
668:
664:
660:
656:
651:
649:
645:
641:
637:
627:
625:
624:Schur numbers
621:
617:
613:
609:
605:
604:Ramsey theory
601:
586:
567:
563:
556:
531:
527:
520:
508:
503:
501:
497:
494:
484:
475:
473:
468:
466:
460:
457:
453:
448:
443:
423:
414:
410:
408:
397:
394:
390:
388:
384:
379:
370:
368:
364:
360:
356:
355:shared-memory
351:
348:
345:and parallel
344:
340:
331:
327:
325:
321:
317:
312:
310:
304:
300:
298:
294:
290:
286:
282:
278:
272:
262:
260:
253:
243:
241:
237:
233:
228:
226:
222:
218:
214:
206:
202:
198:
194:
190:
189:
188:
186:
182:
176:
166:
164:
160:
156:
152:
148:
144:
140:
136:
131:
129:
125:
121:
117:
112:
109:
105:
100:
98:
94:
90:
86:
82:
78:
74:
70:
66:
62:
58:
54:
50:
46:
42:
38:
34:
30:
26:
22:
2775:Isabelle/HOL
2688:
2592:Verification
2575:completeness
2467:Type systems
2410:Control flow
2304:Denotational
2245:Polyvariance
2213:Key concepts
2125:
2115:
2094:
2072:(1): 73–82.
2069:
2065:
2055:
2025:(9): 69–77.
2022:
2018:
2008:
1981:
1977:
1964:
1931:
1927:
1917:
1906:. Retrieved
1902:
1893:
1842:
1838:
1828:
1784:
1778:
1761:
1757:
1751:
1721:(1): 53–61.
1718:
1714:
1704:
1692:
1680:
1645:
1632:
1598:
1592:
1566:
1560:
1527:
1523:
1517:
1473:
1464:
1445:
1429:
1403:
1380:. Retrieved
1376:
1367:
1323:
1317:
1306:. Retrieved
1302:
1293:
1282:. Retrieved
1278:
1269:
1260:
1247:
1221:
1201:. Retrieved
1197:
1188:
1177:. Retrieved
1173:
1164:
1153:. Retrieved
1149:
1140:
1129:. Retrieved
1120:
1109:
1098:. Retrieved
1091:the original
1078:
1074:
1061:
1026:
1013:
974:
967:
942:
938:
932:
904:
858:
852:
836:
811:
807:
801:
793:
761:
755:
695:
688:
652:
633:
616:Marijn Heule
597:
589:Applications
504:
496:local search
490:
481:
478:Local search
469:
461:
439:
403:
395:
391:
380:
376:
352:
347:local search
337:
328:
320:verification
313:
305:
301:
274:
265:CDCL solvers
255:
246:DPLL solvers
231:
229:
224:
220:
216:
212:
210:
204:
200:
196:
192:
185:x, y, z, ...
184:
180:
178:
132:
127:
123:
113:
101:
80:
76:
72:
68:
64:
56:
52:
48:
44:
28:
18:
2704:Lightweight
2566:Side effect
2462:Termination
2316:Operational
2225:Correctness
1934:(1): 7–34.
671:hoare logic
614:. In 2016,
452:disjunction
447:conjunction
281:backjumping
240:NP-complete
221:satisfiable
108:NP-complete
61:satisfiable
2868:Categories
2659:Union-find
2623:Separation
2561:Refinement
2427:Dependence
2326:Small-step
2235:Invariants
2106:2104.08594
1908:2023-10-26
1794:1605.00723
1483:1605.00723
1382:2020-02-13
1333:1505.03340
1308:2020-02-13
1284:2019-12-29
1203:2020-02-13
1179:2020-02-13
1155:2020-02-13
1131:2007-11-15
1100:2015-08-28
1081:(5): 506.
1044:1581132972
814:(3): 201.
747:References
665:, program
507:resolution
493:stochastic
456:equivalent
373:Portfolios
213:assignment
93:heuristics
85:algorithms
29:SAT solver
2755:HOL Light
2585:Languages
2571:Soundness
2490:Data-flow
2472:Typestate
2422:Data-flow
2351:Petri net
2299:Axiomatic
2284:Semantics
2152:232109303
2086:0377-2217
2039:0001-0782
1948:1572-8102
1869:1476-4687
1735:1058-6458
1672:123177576
1552:124272560
1005:195755607
842:Davis, M.
766:CiteSeerX
409:problem.
203:AND (NOT
2853:Glossary
2833:Category
2770:Isabelle
2654:Hashcons
2628:Temporal
2544:Concepts
2384:Analyses
2321:Big-step
2169:Overview
2047:11621980
1877:27251254
1758:Integers
1625:14735849
1524:Integers
1360:11507540
959:10190144
885:15866917
828:31888376
725:See also
644:software
640:hardware
339:Parallel
309:OR-Tools
169:Overview
2843:Outline
2649:E-graph
2522:Testing
2507:Fuzzing
2482:Dynamic
2447:Pointer
1956:2484208
1885:5528978
1847:Bibcode
1821:7912943
1770:3083419
1764:: A46.
1743:1696473
1544:2684128
1510:7912943
1053:9292941
511:runtime
500:WalkSAT
326:(BDD).
234:is the
55:or not
51:) and (
41:Boolean
2618:Linear
2601:Logics
2437:Escape
2392:Static
2338:Models
2150:
2140:
2084:
2045:
2037:
1996:
1954:
1946:
1883:
1875:
1867:
1839:Nature
1819:
1809:
1768:
1741:
1733:
1670:
1660:
1623:
1613:
1581:
1550:
1542:
1508:
1498:
1452:
1418:
1358:
1348:
1236:
1051:
1041:
1003:
993:
957:
921:
883:
826:
786:
768:
199:) OR (
153:, and
2807:Twelf
2797:NuPRL
2792:Mizar
2765:Idris
2712:Alloy
2668:Tools
2608:Hoare
2452:Shape
2405:Alias
2292:Types
2148:S2CID
2101:arXiv
2043:S2CID
1974:(PDF)
1952:S2CID
1881:S2CID
1817:S2CID
1789:arXiv
1739:S2CID
1668:S2CID
1642:(PDF)
1621:S2CID
1548:S2CID
1506:S2CID
1478:arXiv
1442:(PDF)
1356:S2CID
1328:arXiv
1257:(PDF)
1094:(PDF)
1071:(PDF)
1049:S2CID
1023:(PDF)
1001:S2CID
979:(PDF)
955:S2CID
881:S2CID
849:(PDF)
824:S2CID
646:. In
612:FPGAs
602:. In
564:1.307
528:1.308
387:seeds
297:GRASP
293:Chaff
31:is a
2787:LEGO
2782:Lean
2760:HOL4
2740:Agda
2735:ACL2
2717:TLA+
2573:and
2415:kCFA
2138:ISBN
2082:ISSN
2035:ISSN
1994:ISBN
1944:ISSN
1873:PMID
1865:ISSN
1807:ISBN
1731:ISSN
1658:ISBN
1611:ISBN
1579:ISBN
1496:ISBN
1450:ISBN
1416:ISBN
1346:ISBN
1234:ISBN
1039:ISBN
991:ISBN
919:ISBN
784:ISBN
677:and
642:and
318:and
295:and
230:The
195:AND
95:and
75:and
67:and
27:, a
23:and
2802:PVS
2745:Coq
2694:SMT
2689:SAT
2684:CHC
2644:BDD
2130:doi
2074:doi
2070:213
2027:doi
1986:doi
1936:doi
1855:doi
1843:534
1799:doi
1723:doi
1650:doi
1603:doi
1571:doi
1532:doi
1488:doi
1408:doi
1338:doi
1226:doi
1083:doi
1031:doi
983:doi
947:doi
943:103
909:doi
871:hdl
863:doi
816:doi
776:doi
696:In
689:In
638:of
513:of
467:.
365:or
211:An
47:or
19:In
2870::
2750:F*
2146:.
2136:.
2124:.
2080:.
2068:.
2064:.
2041:.
2033:.
2023:54
2021:.
2017:.
1992:.
1982:58
1980:.
1976:.
1950:.
1942:.
1932:19
1930:.
1926:.
1901:.
1879:.
1871:.
1863:.
1853:.
1841:.
1837:.
1815:,
1805:,
1797:,
1766:MR
1762:12
1760:.
1737:.
1729:.
1719:17
1717:.
1713:.
1666:.
1656:.
1644:.
1619:,
1609:,
1577:,
1546:.
1540:MR
1538:.
1528:10
1526:.
1504:,
1494:,
1486:,
1444:.
1414:,
1391:^
1375:.
1354:,
1344:,
1336:,
1301:.
1277:.
1259:.
1232:,
1212:^
1196:.
1172:.
1148:.
1079:48
1077:.
1073:.
1047:.
1037:.
1025:.
999:.
989:.
953:.
941:.
917:,
893:^
879:.
869:.
857:.
851:.
822:.
810:.
792:,
782:,
774:,
721:.
681:.
661:,
299:.
242:.
207:))
179:A
165:.
149:,
145:,
141:,
137:,
126:,
2198:e
2191:t
2184:v
2154:.
2132::
2109:.
2103::
2088:.
2076::
2049:.
2029::
1988::
1958:.
1938::
1911:.
1887:.
1857::
1849::
1801::
1791::
1772:.
1745:.
1725::
1674:.
1652::
1605::
1573::
1554:.
1534::
1490::
1480::
1458:.
1410::
1385:.
1340::
1330::
1311:.
1287:.
1263:.
1228::
1206:.
1182:.
1158:.
1134:.
1103:.
1085::
1055:.
1033::
1007:.
985::
961:.
949::
911::
887:.
873::
865::
859:5
830:.
818::
812:7
778::
573:)
568:n
560:(
557:O
537:)
532:n
524:(
521:O
424:F
217:v
205:z
201:x
197:y
193:x
191:(
128:y
124:x
81:x
77:y
73:x
69:y
65:x
57:y
53:x
49:y
45:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.