Now Reading
The Silent (R)evolution of SAT | June 2023

The Silent (R)evolution of SAT | June 2023

2023-05-25 21:41:54

connected dot pattern

Credit score: Igor Kisselev

The propositional satisfiability drawback (SAT) was the primary to be proven NP-complete by Prepare dinner and Levin. SAT remained the embodiment of theoretical worst-case hardness. Nevertheless, in stark distinction to its theoretical hardness, SAT has emerged as a central goal drawback for effectively fixing all kinds of computational issues. SAT fixing expertise has repeatedly superior since a breakthrough across the millennium, which catapulted sensible SAT fixing forward by orders of magnitudes. Immediately, the numerous flavors of SAT expertise could be present in all areas of technological innovation.

Back to Top

Key Insights

ins01.gif

SAT asks whether or not a given propositional components is satisfiable. That’s, can we set the components’s variables to values 1 (True) or 0 (False) in such a manner that your entire components evaluates to 1? F = (x1x2x3) ∧ (¬x1 ∨ ¬x2 ∨ ¬x3) ∧ (¬x1x2) ∧ (x2x3) is a straightforward propositional components in conjunctive regular kind (CNF), the place x1, x2, and x3 are propositional variables and ∨, ∧, and ¬ check with the logical operators OR (disjunction), AND (conjunction), and NOT (negation), respectively. A variable xi or a negated variable ¬xi is a literal, and a disjunction of literals is a clause. So, the above components F is a conjunction of 4 clauses. The components is satisfiable; we are able to fulfill it by the reality project that units x1 and x2 to 1, and x3 to 0: the primary, third, and fourth clauses are glad by x2 = 1 as a result of the clauses comprise x2. The second clause is glad by x3 = 0 as a result of it comprises ¬x3. In consequence, all clauses are glad. A fact project naturally extends from variables to literals by setting ¬x to the other worth of x. Therefore, a components is satisfiable if and provided that there’s a fact project that units at the very least one literal in every clause to 1.

Example 1 reveals a bigger components that’s unsatisfiable—that’s, not glad by any project. The give attention to CNF formulation just isn’t a restriction. The so-called Tseitin transformation39 effectively transforms any propositional components into CNF with out affecting its satisfiability.

uf1.jpg
Determine. Instance 1. Beneath every of the two9 fact assignments to the variables x1, …, x9, at the very least considered one of G’s clauses evaluates to 0, making the components G unsatisfiable.*

At first look, the SAT drawback appears to be like inconspicuous since it’s easy to state, doesn’t look troublesome to unravel, and appears uninteresting for sensible functions. Nonetheless, Stephen Prepare dinner7 and Leonid Levin29 confirmed independently within the Nineteen Seventies that SAT is NP-complete, making it the primary NP-complete drawback. So, suppose one might remedy SAT in polynomial time on arbitrary enter. In that case, one might additionally remedy any NP-complete drawback in polynomial time, and it might observe that P equals NP. Thus, when it comes to worst-case complexity idea, SAT embodies computational hardness. Additionally, in fashionable complexity idea, SAT continues to function a tough benchmark drawback within the type of the (Sturdy) Exponential Time Speculation.4

In stark distinction to its theoretical worst-case hardness, the SAT drawback has emerged as a vital instrument for effectively fixing all kinds of computational issues, starting from {hardware} and software program verification to planning, combinatorial design, and software program dependency.1,4 On this manner, SAT considerably impacts in the present day’s technological innovation. SAT is broadly utilized in data illustration, reasoning,19 and synthetic intelligence (AI).9 Though SAT is principally related to symbolic AI, it contributes to non-symbolic AI by offering model-counting algorithms, that are important instruments for probabilistic reasoning,9 and allocates a essential spine for neurosymbolic AI.24 Notably, utilizing SAT, long-standing open issues in mathematical combinatorics had been efficiently solved—for instance, the Pythagorean Triples Drawback.4,21 Fixing such difficult issues with SAT requires the power to effectively translate the unique drawback into an occasion of the SAT drawback and the provision of laptop packages, known as SAT solvers, which effectively consider SAT cases. Preliminary progress in sensible SAT fixing started within the early Nineteen Nineties, resulting in a breakthrough across the millennium. The final 20 years have introduced additional monumental technological development and innovation to SAT fixing. Immediately, SAT solvers are so highly effective and strong that they’ve turn out to be major instruments for fixing exhausting computational issues. Solvers have been embedded into advanced procedures to unravel extra advanced issues, resembling optimization issues (MaxSAT, Pseudo-Boolean Optimization) or quantified satisfiability (QSAT).

“The story of satisfiability is the story of a triumph of software program engineering, blended with wealthy doses of lovely arithmetic,” writes Donald E. Knuth within the preface to the second a part of the fourth quantity of The Artwork of Pc Programming,28 which comprises a piece on satisfiability that stretches properly over 300 pages.

As we noticed unbelievable advances in laptop {hardware}, yielding ever-faster processors, giant and environment friendly reminiscence, and massively parallel computing items, one might ask whether or not progress in SAT fixing is the only results of {hardware} development. A current Time Leap Problem addressed this query by operating a race between 20-year-old SAT solvers on new laptop {hardware} and fashionable SAT solvers on 20-year-old laptop {hardware}.16 The experiments verify Knuth’s assertion on engineering and arithmetic. Though {hardware} enhancements make outdated solvers sooner, algorithmic progress dominates and drives in the present day’s SAT fixing.

This text goals to make clear the persevering with progress of sensible SAT fixing by means of a collection of evolutionary improvements and enhancements which have been ongoing because the revolutionary breakthrough across the millennium. General, we argue that SAT has earned the title of a silent (r)evolution. We inform the story of SAT divided into three eras: the pre-revolution, the revolution, and the evolution.

Back to Top

Eras of Sensible SAT Fixing

Period I: The pre-revolution. The constructing blocks of in the present day’s SAT success are varied and date again even to the primary half of the 20th century. We check with different sources for an in depth description of SAT’s historical past4 and give attention to just a few vital milestones of the fashionable period. Full and incomplete solvers had been the prevalent SAT solvers within the Nineteen Nineties. Incomplete solvers, based mostly on stochastic native search,23 had been efficiently utilized to planning issues4 and satisfiable cases. In distinction, full solvers, based mostly on backtracking search, had been used to unravel combinatorial issues (resembling puzzles, N-queens, and Latin squares) in addition to uniform random k-SAT formulation (together with unsatisfiable ones). These early full solvers adopted the final method, known as DPLL, which was first proposed by Davis, Logemann, and Loveland (DLL) as a memory-efficient refinement of an earlier algorithm by Davis and Putnam (DP).a,11,12

In fashionable terminology, DPLL is a backtracking algorithm that performs a depth-first exploration of a binary search tree on fact assignments (see Example 2). It applies the next two optimization steps repeatedly after a variable has been assigned, propagating the present partial project: if the present project units all however one literal of a clause to 0 (the clause is a unit clause), then we are able to safely set the remaining unassigned literal to 1—unit propagation is the repeated software of this course of; if the present project satisfies all clauses containing some uassigned literal, then we are able to safely set that literal to 0—the other literal known as a pure literal. Backtracking happens when the present partial project units all of the literals of a clause to 0.

uf2.jpg
Determine. Instance 2. Search Tree: Illustration of a potential run of the DPLL algorithm on the components G from Example 1. Circles point out resolution variables, and unit propagation is represented by the listing of propagated literals. After acquiring inconsistency () in a single department, DPLL chronologically backtracks to the final resolution, which in our instance causes the search to run into the identical battle a number of instances.

Heuristic strategies that resolve when and the way variables are assigned play an important position within the context of DPLL.8

Early implementation challenges. Three SAT competitions had been organized within the Nineteen Nineties. The second competitors, 1993’s DIMACS implementation problem,4 launched the usual ASCII enter format for SAT solvers, which remains to be in use. This standardized enter format helps reusing SAT solvers as black packing containers and sharing benchmarks. The DIMACS CNF format describes a propositional components. The preamble supplies the format (CNF), the variety of variables, and the variety of clauses. The remaining traces denote clauses, the place every literal is represented by a signed integer, utilizing 0 as a separator. Example 3 illustrates our operating instance containing 9 variables and 17 clauses within the DIMACS CNF format.

uf3.jpg
Determine. Instance 3. DIMACS CNF illustration of Example 1‘s components G. Do that instance at http://bit.ly/406Lqc7 utilizing as an illustration kissat SAT solver http://bit.ly/3oa8zx9 to unravel it with an actual SAT solver.

Period II: The revolution. The primary pillar of the revolution30 was the solver GRASP,31 which proposed a brand new structure, combining non-chronological backtracking, battle evaluation, and studying, in the present day known as battle pushed clause studying (CDCL). CDCL is extra than simply DPLL with studying, since it’s not a pure backtracking search. It captures unit propagation in a directed acyclic implication graph that’s used to carry out battle evaluation and clause studying, which prominently drives the search. Fashionable SAT solvers use the path information construction proposed by MiniSat13 to seize the search tree and the implication graph.

The second pillar was the CDCL-based solver Chaff,32 specifically designed to unravel giant benchmark cases by taking the traits of the host laptop into consideration and attaining an unprecedented steadiness between the sophistication of algorithms and information buildings on the one aspect and the sensible effectivity on the opposite. Chaff launched the Watched Literal information construction, a “lazy” scheme for performing unit propagation that allowed cost-free backtracking. The branching heuristics (VSIDS) and battle evaluation process had been fastidiously designed with a brand new tradeoff between reasoning energy and computation value: The emphasis on current conflicts results in a locality-based search.

We illustrate CDCL for our operating instance in Example 4. Many battle clauses are realized through the search, which is kind of demanding on reminiscence. Fashionable CDCL solvers continuously delete realized clauses and heuristically predict those to maintain.4 Varied heuristics, resembling VSIDS,32 EVSIDS,13 or LRB,4 can be found for optimizing the search and assigning the variables. These heuristics impose low overhead, generate virtually no value for backtracking, and are up to date when studying clauses. To flee unfortunate search tree exploration through the search, solvers continuously unassign all variables and restart the search (however preserve the realized clauses). Frequent heuristic schemes that resolve when to restart are Luby or Fast Restarts.4 Additionally, machine-learning strategies have been used to optimize heuristics.4 Nonetheless, extra cautious evaluation is required to higher perceive how the elements of the solver and their interplay have an effect on its general effectivity.14,27

uf4.jpg
Determine. Instance 4. Propagation Graph: Hint of a potential CDCL run on the components G from Example 1.

Some important functions drew a lot consideration to sensible SAT fixing from academia and trade. For instance, bounded mannequin checking (BMC)4 supplied quite a few difficult benchmarks, which had been quickly tackled. BMC, which checks the correctness of sequential programs over a bounded variety of steps, was proposed after the failure of normal mannequin checking with binary resolution diagrams (BDDs), a graph-based canonical illustration of propositional formulation.6 The BMC benchmarks had been intensive, with tens of hundreds of variables and clauses. Combining conflict-driven heuristics with battle evaluation (CDCL) might remedy BMC benchmarks as much as two orders of magnitude sooner than every other method. These spectacular outcomes utilized to different software benchmarks as properly. The pc-aided verification (CAV) group acknowledged the central position of GRASP and Chaff for that excellent progress by presenting their authors with the CAV 2009 award for “elementary contributions to the event of high-performance Boolean satisfiability solvers.”

Period III: The evolution. Whereas bettering solvers is a crucial objective, the group has progressed in new modeling strategies and strategies for certifying outcomes.

Environment friendly SAT encodings. It’s difficult to precise a computational drawback as a CNF components that the solver can remedy effectively. Encodings might blow up the ensuing CNF components fairly notably, leading to quadratic, cubic, and even worse overhead in comparison with the unique drawback occasion. Often, one faces a tradeoff between area and ease. Intuitively, one would attempt to preserve the occasion as small and concise as potential, balancing the variety of variables and the variety of clauses. If we have now n variables and add m auxiliary variables, the potential search area grows from 2n to 2n+m. Nonetheless, in observe, including such variables can cut back the variety of clauses, thereby rushing up the search.4 An analogous sample was noticed by early automated take a look at pattern-generation packages, resembling path-oriented resolution making (PODEM).4 That is notably related when encoding properties that constrain the variety of variables from a set of variables that have to be set to 1, known as cardinality constraints. We give a easy instance in Example 5.

uf5.jpg
Determine. Instance 5. Encoding strategies based mostly on binary adders.37

Assumptions. Utilizing SAT solvers as “oracles” is much extra advanced in observe than simply having an NP oracle in theoretical concerns. On the one hand, as profitable as SAT solvers are, they aren’t NP oracles. SAT solvers want time for fixing and will not even reply inside an inexpensive time. Then again, fashionable SAT solvers are extra subtle than NP oracles. They admit stateful procedures, the place clauses could also be added or eliminated throughout fixing. To manage added clauses with out invalidating realized clauses, fashionable solvers assist assumptions, popularized by MiniSat,13 that are further literals launched for representing the state of clauses. It turned out that assumptions are extremely versatile and helpful. We exhibit assumptions in Example 6.

uf6.jpg
Determine. Instance 6. Assumptions make our operating components satisfiable once more.

Inprocessing/preprocessing. SAT solvers run varied simplification guidelines to remove pointless variables or clauses. A number of simplification guidelines exist; some could be carried out in linear time whereas others require quadratic time. Extraordinarily helpful is preprocessing, the place the occasion is simplified earlier than the precise solver is began.4 Curiously, one such preprocessing activity is to run a restricted type of the Davis-Putnam process on a subset of variables (bounded variable elimination). Nevertheless, fashionable solvers resembling Lingeling implement extra subtle guidelines, that are run through the search earlier than the subsequent variables are assigned (inprocessing) and take realized clauses into consideration.4 Extra time-consuming inprocessing strategies resembling equivalence studying, cardinality constraints, or parity detection could be utilized with a restricted finances and interleaved with search.

Parallel fixing. Within the 2000s, Moore’s legislation began approaching its limits in CPU efficiency on single cores, and the clock-speed enhancements for silicon-based chips began to decelerate. Parallel computation was one approach to compensate for this pattern, and it discovered its manner into client {hardware}. Across the identical time, parallel computing additionally began to turn out to be extra modern in SAT fixing, aiming to enhance general processing efficiency and sort out large cases.21 The 2 essential strategies that developed are parallel-portfolio and divide-and-conquer fixing.

In parallel-portfolio fixing, an issue occasion is independently given to a group of solvers competing for an answer in parallel. Often, the gathering contains completely different solvers or one solver with completely different heuristics. Whereas parallel SAT solvers optimize efficiency to unravel giant cases, they might produce completely different satisfying assignments or unsatisfiability proofs for a given enter components as a result of they’re inherently non-deterministic resulting from race circumstances. However, some current parallel solvers obtain determinism with an inexpensive runtime overhead. Determinism is important for functions requiring reproducibility, resembling scheduling or mannequin checking. Over the past years, large parallelization utilizing graphics processing items (GPUs) or tensor processing items (TPUs) has turn out to be a well-liked method in laptop science and ML. Facets of recent SAT fixing have been efficiently applied and examined on GPUs, together with solvers tailor-made for counting the variety of satisfying assignments.17 Nonetheless, SAT fixing has not but benefited from large parallelization.

Divide-and-conquer divides a components into a number of formulation. The workload is shared amongst a number of solvers that run in parallel and might even synchronize realized clauses. Nevertheless, fashionable sequential SAT solvers don’t have to exhaust the search area to discover a resolution or refute a components; realized clauses enable for shortcuts, making it exhausting to decompose cases due to the elevated synchronization efforts for realized clauses. A well-liked model is cube-and-conquer, which partitions an occasion by a look-ahead approach into as much as 1,000,000 sub-instances after which solves the sub-instances with a CDCL-based solver.21

Correctness of solvers and emitting proofs. The outcomes of early SAT solvers had been exhausting to validate. Whereas it’s straightforward to examine whether or not an project returned by a solver satisfies the given components, up to now, no approach was accessible to confirm correctness if the solver claimed that an occasion is unsatisfiable. In the course of the first competitions, one might solely examine whether or not emitted assignments had been right and that solvers didn’t present inconsistent outcomes. If solver A outputs “satisfiable” and solver B outputs “unsatisfiable” on the identical components, one would examine whether or not the project given by A certainly satisfies the components. In that case, solver B is wrong; in any other case, solver A is wrong, however nothing could be concluded about solver B. Solver correctness has been addressed by intensive testing, together with fuzzing and asking for traces that give rise to an unsatisfiability proof inside a devoted propositional proof system.4 Such traces could be mechanically checked utilizing third-party instruments, which could be specified, applied, and totally verified. The connection between CDCL runs and propositional proof programs is now properly understood. All of the related proof programs depend on the decision rule, which derives a brand new clause from two clauses containing precisely one reverse literal. For example, in Example 4, the clause c18 = x1 could be derived by decision from c4 = x1 ∨ ¬x7 and c11 = x1x7; clause ¬x1x6 could be derived by decision from c17 = x7x6 ∨ ¬x1 and c15 = x6 ∨ ¬x7 ∨ ¬x1. In idea, CDCL-solvers observe decision proofs that reuse derived clauses (DAG-like decision).3,34 They are often exponentially extra succinct than tree-like decision proofs, similar to DPLL-solvers.4 Within the early 2000s, strategies to make sure the correctness of unsatisfiability outcomes utilizing variants of decision proofs had been offered.4 Nevertheless, they had been invasive to the solver and produced monumental proofs. Within the 2010s, strategies emerged that present proofs which can be compact, straightforward to emit, could be checked effectively, and supply excessive expressiveness. One fashionable proof format is Deletion and Decision Uneven Tautology (DRAT).4 Example 7a supplies a DRAT proof for our operating instance however makes use of solely a fraction of DRAT’s options.

uf7.jpg
Determine. Instance 7. Illustration of a DRAT proof for our operating instance.

Drawback decomposition and verification. Drawback decomposition and verification had been a game-changer for fixing long-standing open math issues utilizing SAT expertise—for instance, invalidating a speculation on Pythagorean triples.22 As described beforehand, fashionable SAT solvers emit proofs that cowl all varieties of current fixing strategies, together with preprocessing and inprocessing. A proof of a mathematical assertion such because the propositional Pythagorean triples drawback could be longer than 200TB, which is extra information than the Hubble Area Telescope gathered in about 20 years. Such proofs are clearly past human understanding and never human-verifiable merely due to their size however can nonetheless be mechanically checked. Consequently, it results in utilizing SAT solvers as brute-force expertise for mathematical functions. This progress in SAT fixing fulfills, lastly, among the early guarantees in automated reasoning and deduction from the Nineteen Sixties.

Fashionable competitions and open supply. Since 2002, the SAT group has organized annual aggressive occasions that encourage novel solver design and collect new benchmark cases.26 Competitions proceed to affect progress in solver improvement and supply a approach to independently assess the effectivity of submitted solvers. In 2002, few solvers used the CDCL structure (4 out of 19). Solvers weren’t strong, and plenty of of them crashed through the competitors—for instance, on cases with many variables, many clauses, or very lengthy clauses. Luckily, this modified the next 12 months resulting from varied broadly accessible benchmarks and revealed anticipated outcomes. Initially, many solvers had been closed supply. Strict submission necessities and the success of the free solver MiniSat13 shifted the group to open supply. MiniSat code was easy to learn, compact, and designed for extendibility. It applied CDCL and outperformed all different solvers in 2005 resulting from minimizing realized clauses and the preprocessor SatELite.4 Over time, the open supply precept enabled researchers to implement their concepts on prime of the most effective accessible solvers and perceive essential implementation particulars normally not shared in papers. As of 2023, offsprings of MiniSat, resembling Glucose, MapleSAT, and MapleCOMSPS, nonetheless take part within the SAT competitors. Whereas competitions repeatedly elevate requirements in environment friendly fixing, there isn’t any single greatest solver in observe. Varied solvers carry out otherwise relying on the thought-about class of benchmarks or the configuration of their inside heuristics. This range could be exploited by programs resembling SATzilla,4 which predict the efficiency of current solvers and choose essentially the most promising ones. A extra subtle method is automated algorithm choice and tuning. Instruments resembling AUTOFOLIO or SMAC4 discover good parameters for a given solver on a goal set of benchmarks.

Theoretical understanding of environment friendly fixing. In 2014, Moshe Vardi identified the dearth of theoretical understanding of the success in sensible SAT fixing.40 In the meantime, the understanding improved from varied viewpoints.18 Solvers are well-engineered, always improved, and effectively remedy many lessons of real-world cases. Nonetheless, they carry out poorly on sure random and cryptographic cases. A regular view is that industrial cases comprise a “hidden construction” that the SAT solver manages to make use of implicitly. Any theoretical evaluation that ignores structural properties of the SAT occasion therefore can’t match up with the empirically noticed solver efficiency. This shortcoming led to a number of analysis traces aiming to seize the hidden construction in a SAT occasion mathematically. One line focuses on capturing construction that correlates properly with empirically noticed solver efficiency.2 This supplies a statistical correlation however no assure that each SAT occasion that reveals this construction is solved rapidly. One other line of analysis takes a causal method; it makes use of the theoretical framework of parameterized complexity to acquire asymptotic efficiency ensures for algorithms that explicitly detect and exploit the hidden construction.4 The underlying fixed-parameter algorithms are particular to the parameter into account and customarily don’t intention at offering a theoretical rationalization of CDCL-solver efficiency.

Back to Top

The Artwork of Utilizing SAT Solvers

A SAT solver could be seen as a robust engine; nevertheless, reaching an answer or guaranteeing that there’s none requires greater than an engine alone. Due to this fact, the SAT group developed modern and highly effective strategies for utilizing and adapting SAT engines.

Single-call fixing. Static encodings rework an enter occasion of the issue of curiosity right into a CNF components. Encoding could be achieved in a high-level programming language resembling Python, which produces a DIMACS CNF file. Barely higher-level entry could be obtained by PySAT,25 a well-liked Python library for encoding issues and utilizing state-of-the-art SAT solvers. SAT engines are extremely optimized on the low-level DIMACS CNF format for squeezing out each ounce of efficiency. Over time, engineers have shifted to extra human-readable and reusable languages; some transcend the propositional case. Examples embody the ASP enter language19 or the MiniZinc constraint modeling language.38 The “Chosen Formalisms…” sidebar on the earlier web page lists different formalisms that concentrate on modeling and drawback fixing with extra expressive languages. Nonetheless, detailed area data and the talent of effectively driving the engine are sometimes useful.

Multi-call fixing. Fashionable SAT solvers can transcend single-call fixing. Many such solvers can modify an already-solved components, reusing data from a earlier fixing course of (incremental fixing) and outputting a subset of the enter clauses that stay unsatisfiable (unsatisfiable core). A few of these strategies resulted in environment friendly fixing strategies for drawback formalisms past SAT, the place the SAT engine drives the fixing course of. The “Propositional Issues” sidebar on this web page lists such chosen formalisms on the propositional degree.

SAT solvers as subroutines. Many exhausting computational issues of sensible significance, notably in AI, are past NP. An unexpectedly profitable software of SAT solvers comes when it comes to QBF solvers for the QSAT drawback (“Propositional Issues” sidebar). A number of profitable QBF solvers, resembling CAQE and RAReQS,4 make use of SAT solvers. RAReQS makes use of two interacting SAT solvers internally to find out the validity of the QSAT occasion. Every solver acts because the existential or the common participant in a two-player recreation. The SAT solvers drive the process: The fashions discovered refine the abstraction of the gamers. This generic method known as Counter Instance Guided Abstraction Refinement (CEGAR). Different profitable QBF solvers, resembling DepQBF4 and Qute,33 lengthen the CDCL process to the quantified case, with particular strategies for figuring out and coping with the dependencies between variables imposed by the quantifiers. In {hardware} or software program verification, the model-checking software IC35 goes additional than discovering bugs by proving security properties. IC3 makes use of incremental SAT to examine the reachability of states from each the preliminary states and the states of curiosity. A special taste of multi-call fixing can be utilized for optimization issues, that are too giant to be encoded right into a single SAT or MaxSAT occasion and the place optimum options are out of attain. The SAT-based Native Enchancment Methodology (SLIM) begins with an preliminary resolution supplied with some normal heuristics. Then, SLIM repeatedly replaces native elements with improved options obtained by a SAT or MaxSAT solver. The strategy has been efficiently utilized for graph decomposition, decision-tree induction, and Bayesian Community construction studying.35

Core-guided optimization. SAT solvers also can remedy optimization issues for minimizing or maximizing an goal operate. For example, such a operate might depend the variables from a subset of variables set to 1. Incremental fixing supplies the means to optimize with a SAT solver: The solver is utilized by progressively including increasingly more clauses that additional constrain the occasion till it turns into unsatisfiable. Recall {that a} SAT solver can present for an unsatisfiable occasion with an unsatisfiable core.4 To fulfill the utmost variety of clauses, at the very least one clause from the unsatisfiable core must be disregarded. This may be expressed utilizing assumptions, a method known as core-guided optimization. Notably, core-guided optimization could be very profitable when fixing issues resembling MaxSAT, the issue of maximizing the variety of glad clauses (Prepositional Issues sidebar). Example 8 describes using gentle clauses on our operating instance, which is the premise for MaxSAT. A well-liked method for MaxSAT fixing makes use of as a subroutine the computation of a minimal hitting set on unsatisfiable cores, normally achieved utilizing a Combined-Integer Programming (MIP) solver.

uf8.jpg
Determine. Instance 8. Gentle clauses enable us to cope with inconsistent necessities.

Back to Top

Outlook

Over the past 20 years, SAT fixing strategies have modified how we sort out exhausting computational issues. The SAT revolution is considerably much less recognized than the celebrated success of machine studying with its ubiquitous and broadly reported affect on expertise and society. SAT solvers have influenced fashionable expertise extra silently. They’re utilized in computational biology,20 for planning,4 to confirm fashionable {hardware},4 working programs, software program,4 and even mathematical statements.4 This makes SAT essential to the progress of recent data expertise. Nonetheless, important Pc Science challenges associated to SAT fixing are nonetheless forward: How can we additional enhance parallel search to take full benefit of recent massively parallel {hardware}? Why does SAT fixing typically work so properly in observe, and what characterizes the instances the place it struggles? How can we enhance the method of developing with good encodings? Lastly, will SAT be broadly utilized additionally to computational physics, chemistry, or non-symbolic AI? To some extent, the revolutions of SAT and machine studying are complementary. There’s a lot potential in combining the 2.

Back to Top

Acknowledgments

This work was carried out whereas the authors visited the Simons Institute for the Concept of Computing. It has been supported by a Google Fellowship on the Simons Institute; the Austrian Science Fund (FWF); Grants J4656, Y698, and P32830; and the Vienna Science and Know-how Fund, Grant WWTF ICT19-065.

Back to Top

References

1. Abate, P. et al. Dependency fixing: A separate concern in part evolution administration. J. Programs and Software program 85, 10 (2012), 2228–2240.

2. Ansótegui, C. et al. Group construction in industrial SAT cases. J. Synthetic Intelligence Analysis 66 (2019), 443–472.

3. Atserias, A., Fichte, J.Ok., and Thurley, M. Clause-learning algorithms with many restarts and bounded-width decision. J. Synthetic Intelligence Analysis 40, 1 (2011), 353–373.

4. A. Biere, M. Heule, H. van Maaren, and T. Walsh, (Eds.). Handbook of Satisfiability (2nd Version). IOS Press, Amsterdam, Netherlands (2021).

5. Bradley, A.R. SAT-based mannequin checking with out unrolling. In Verification, Mannequin Checking, and Summary Interpretation-12th Intern. Conf. Proceedings (Lecture Notes in Pc Science 6538), R. Jhala and D.A. Schmidt (Eds.). Springer (January 2011), 70–87.

6. Bryant, R.E. Graph-based algorithms for Boolean operate manipulation. IEEE Transactions in Computing C-35, 8 (August 1986), 677–691.

7. Prepare dinner, S.A. The complexity of theorem-proving procedures. In Proceedings of the threerd Annual Symp. on Concept of Computing, ACM (1971), M.A. Harrison, R.B. Banerji, and J.D. Ullman (Eds.) 151–158.

8. Prepare dinner, S.A. and Mitchell, D.G. Discovering exhausting cases of satisfiability drawback: A survey. DIMACS Sequence in Discrete Arithmetic and Theoretical Pc Science 5 (1997).

9. Darwiche, A. Three fashionable roles for logic in AI. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symp. on Ideas of Database Programs (2020), 229–243.

10. Darwiche, A. and Marquis, P. A data compilation map. J. Synthetic Intelligence Analysis 17, 1 (2002), 229–264.

11. Davis, M., Logemann, G., and Loveland, D. A machine program for theorem-proving. Communications of the ACM 5, 7 (July 1962), 394–397.

12. Davis, M. and Putnam, H. A computing process for quantification idea. J. of the ACM 7, 3 (1960), 201–215.

13. Eén, N. and Sörensson, N. An extensible SAT-solver. In Proceedings of the 6th Intern. Conf. on Concept and Functions of Satisfiability Testing, E. Giunchiglia and A. Tacchella (Eds.), Springer Verlag (2003), 502–518.

14. Elffers, J. et al. In search of sensible CDCL insights from theoretical SAT benchmarks. In Proceedings of the 27th Intern. Joint Conf. on Synthetic Intelligence, J. Lang (Ed.), (2018), 1300–1308.

15. Fichte, J.Ok., Hecher, M., and Hamiti, F. The mannequin counting competitors 2020. ACM J. Experimental Algorithmics 26, 13 (December 2021).

16. Fichte, J.Ok., Hecher, M., and Szeider, S. A time leap problem for SAT-solving. In Proceedings of the 26th Intern. Conf. on Ideas and Follow of Constraint Programming, H.Simonis (Ed.). Springer Verlag, Louvain-la-Neuve, Belgium (2020), 267–285.

17. Fichte, J.Ok., Hecher, M., and Zisser, M. An improved GPU-based SAT mannequin counter. In Proceedings of the 25th Intern. Conf. on Ideas and Follow of Constraint Programming, T. Schiex and S. de Givry (Eds.), (2019), 491–509.

18. Ganesh, V. and Vardi, M.Y. Past the Worst-Case Evaluation of Algorithms. Cambridge College Press, (2021), 547–566.

19. Gebser, M. et al. Reply Set Fixing in Follow. Morgan & Claypool (2012).

20. Guerra, J. and Lynce, I. Reasoning over organic networks utilizing most satisfiability. In Proceedings of the 18th Intern. Conf. Ideas and Follow of Constraint Programming (Lecture Notes in Pc Science 7514), M. Milano (Ed.). Springer Verlag, Québec Metropolis, QC, Canada (2012), 941–956.

21. Hamadi, Y. and Sais, L. (Eds.). Handbook of Parallel Constraint Reasoning. Springer (2018).

22. Heule, M.J.H. and Kullmann, O. The science of brute power. Communications of the ACM 60, 8 (July 2017), 70–79.

23. Hoos, H.H. and Stützle, T. In the direction of a characterisation of the behaviour of stochastic native search algorithms for SAT. Synthetic Intelligence 112, 1 (1999), 213–232.

24. Ignatiev, A. et al. Reasoning-based studying of interpretable ML fashions. In Proceedings of the 30th Intern. Joint Conf. on Synthetic Intelligence, Zhi-Hua Zhou (Ed.), (August 2021), 4458–4465.

25. Ignatiev, A., Morgado, A., and Marques-Silva, J. PySAT: A Python toolkit for prototyping with SAT oracles. In Proceedings of the 21st Intern. Conf. on Concept and Functions of Satisfiability Testing (Lecture Notes in Pc Science 10929), O. Beyersdorff and C.M. Wintersteiger (Eds.). Springer Verlag (2018), 428–437.

26. Järvisalo, M. et al. The Worldwide SAT Solver Competitions. AI Journal. The AAAI Press (2012).

27. Katebi, H., Sakallah, Ok.A., and Marques-Silva, J.P. Empirical examine of the anatomy of recent SAT solvers. In Proceedings of the 14th Intern. Conf. on Concept and Functions of Satisfiability Testing (Lecture Notes in Pc Science 6695), Ok.A. Sakallah and L. Simon (Eds.). Springer Verlag (2011), 343–356.

28. Knuth, D.E. The Artwork of Pc Programming Vol. 4B, Combinatorial Algorithms, Half 2. Addison-Wesley (2023).

29. Levin, L. Common sequential search issues. Issues of Data Transmission 9, 3 (1973), 265–266.

30. Malik, S. and Zhang, L. Boolean satisfiability from theoretical hardness to sensible success. Communications of the ACM 52, 8 (August 2009), 76–82.

31. Marques-Silva, J. and Sakallah, Ok.A. GRASP: A search algorithm for propositional satisfiability. IEEE Trans. Comput. 48, 5 (Could 1999), 506–521.

32. Moskewicz, M.W. et al. Chaff: Engineering an environment friendly SAT solver. In Proceedings of the 38th Annual Design Automation Conf., J. Rabaey (Ed.). Affiliation for Computing Equipment (2001), 530–535.

33. Peitl, T., Slivovsky, F., and Szeider, S. Dependency studying for QBF. J. Synthetic Intelligence Analysis 65 (2019), 180–208.

34. Pipatsrisawat, Ok. and Darwiche, A. On the ability of clause-learning SAT solvers as decision engines. Synthetic Intelligence 175, 2 (2011), 512–525.

See Also

35. Ramaswamy, V.P. and Szeider, S. Turbocharging treewidth-bounded Bayesian community construction studying. In Proceedings of the 35th AAAI Conf. on Synthetic Intelligence, The AAAI Press (2021), 3895–3903.

36. Rossi, F., van Beek, P., and Walsh, T. Handbook of Constraint Programming. Elsevier Science Publishers, North-Holland, USA (2006).

37. Sinz, C. In the direction of an optimum CNF encoding of Boolean cardinality constraints. In Proceedings of the 11th Intern. Conf. on Ideas and Follow of Constraint Programming (Lecture Notes in Pc Science 3709), P. van Beek (Ed.). Springer Verlag, Sitges, Spain (2005), 827–831.

38. Stuckey, P.J. et al. The MiniZinc Problem 2008–2013. AI Journal 35, 2 (June 2014), 55–60.

39. Tseytin, G.S. On the complexity of derivation in propositional calculus. Automation of Reasoning: Classical Papers in Computational Logic 2 (1983), 466–483.

40. Vardi, M.Y. Boolean satisfiability: Concept and engineering. Communications of the ACM 57, 3 (March 2014), 5.

Back to Top

Authors

Johannes Ok. Fichte is an affiliate professor at IDA, Institutionen för datavetenskap, Linköping College, Sweden.

Daniel Le Berre is a professor at Artois College and CNRS, Centre de Recherche en Informatique de Lens, France.

Markus Hecher (hecher@mit.edu) is a PostDoc on the Pc Science & Synthetic Intelligence Laboratory, Massachusetts Institute of Know-how, Cambridge, USA.

Stefan Szeider is a professor and head of the Algorithms and Complexity Group at TU Wien, Vienna, Austria.

Back to Top

Footnotes

a. DPLL combines DP and DLL to emphasise each contributions.

Back to Top

Back to Top


cacm_ccby-ncnd.gif This work is licensed underneath a Inventive Commons Attribution-NonCommercial-NoDerivs Worldwide 4.0 License

The Digital Library is revealed by the Affiliation for Computing Equipment. Copyright © 2023 ACM, Inc.


No entries discovered

Source Link

What's Your Reaction?
Excited
0
Happy
0
In Love
0
Not Sure
0
Silly
0
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top