SAT and SMT Solvers Explained: How Computers Solve Complex Logical and Mathematical Problems

Introduction

Computing systems often face many scenarios where there are multiple possibilities to find a correct answer. Computers have to solve problems such as finding logical errors in software, verifying complex hardware designs, and scheduling by determining if a combination can satisfy the conditions. Finding an answer to these problems manually can be very challenging, especially when there are thousands or millions of possibilities. Satisfiability (SAT) and Satisfiability Modulo Theories (SMT) solvers can help. These are special programs that use logical mathematics and reasoning to determine if a set of statements can be satisfied. They can help computers find solutions to problems.

SAT and SMT solvers are closely related to formal methods, artificial intelligence, mathematics and computer science. A SAT solver is used to identify if a boolean expression can be satisfied by assigning the right values to the variables. An SMT solver adds more theories to this. This allows them to reason about numbers, equations, arrays, data structures and more. An example could be using a SAT solver to identify if a set of logical conditions can all be true. An SMT solver will also determine if numerical conditions such as age, cost, distance and time can be satisfied.

To understand these technologies we first need to learn about Boolean Satisfiability.

What is Boolean Satisfiability (SAT)?

Boolean Satisfiability (often referred to as SAT) is a fundamental problem in computer science and mathematical logic. It aims to determine if a boolean expression can be satisfied by assigning the right values to each variable. A Boolean variable can only ever be either true or false (represented numerically as 1 and 0). Logical operators such as AND, OR and NOT will be used to create expressions. A SAT problem is trying to determine if there is a solution where the expression is true. If there is, the expression can be satisfied. If there isn’t, then the expression is unsatisfiable.

An example would be a boolean expression such as (A OR B) AND (NOT A OR C). The SAT solver will look at all the possible combinations of values A, B and C can be. In this example A = true, B = false, C = true can satisfy both parts of the expression, meaning that it can be satisfied. If the conditions were written so that a variable had to be both true and false the solver would know there is no valid combination.

The SAT problem is very important in theoretical computer science as it was the first problem shown to be NP-complete. This means that it falls into a group of problems where it can be verified in polynomial time. All problems in NP can be converted into a SAT problem with a polynomial conversion.Whilst this doesn’t mean that all SAT problems are challenging to solve, it shows why they are relevant to many computer science problems. Researchers and software developers will often use SAT to help them represent a complex problem mathematically.

How SAT Solvers Work

SAT solvers will look at the logical relationships between the variables and try to find a solution that satisfies all the conditions. Modern SAT solvers will use complex algorithms to help them avoid impossible combinations, find contradictions and reduce the amount of unnecessary calculations. A common way an SAT solver will represent the problem is with Conjunctive Normal Form. This is when the expression is broken down into clauses connected with AND. Each clause will contain one or more boolean variables or negations connected with OR.

An example would be:

(A OR B) AND (NOT A OR C) AND (B OR C)

The solver will look for values for A, B and C that will make each clause true. They can start by assigning a value to one variable and seeing what effect it will have on the rest. If an assignment makes a clause impossible to satisfy then the solver can disregard this option and look at another one. This helps to reduce the amount of combinations that need to be checked. With larger expressions that contain thousands of variables and clauses this can greatly improve performance.

Modern SAT solvers often use algorithms based around DPLL (Davis-Putnam-Logemann-Loveland) and Conflict-Driven Clause Learning (CDCL). DPLL will look at all the possible combinations of variables using logical algorithms. They will use unit propagation and backtracking to help avoid invalid choices. Unit propagation occurs when a clause only has one variable left that can make it true. This means that they can easily assign this value. CDCL will further improve this by looking at contradictions. They will add extra clauses to avoid similar issues and will use smart methods of choosing variables. This means modern SAT solvers can now solve large and complex logical expressions.

What is an SMT Solver?

Satisfiability Modulo Theories (often referred to as SMT) is an extension of Boolean Satisfiability. It allows computers to reason about more complex mathematical and logical relationships. Whilst a SAT solver will only look at Boolean variables, an SMT solver can use additional theories. These theories allow them to understand relationships between integers, real numbers, inequalities, arrays, bit-vectors and more. This means that they can solve problems that include logical conditions and mathematical constraints.

Imagine if a computer had to determine if an employee could attend a meeting. This could be due to having to be available after 10am, finishing before 12pm and completing another task. A basic SAT solver could be used to represent this with boolean statements but wouldn’t understand the relationship between the start and finish times and length of the meeting. An SMT solver can include numerical constraints which can help determine if there is a valid solution. This makes them particularly useful for software verification.

SMT solvers often use a combination of Boolean reasoning and specialized methods for mathematical theories. The Boolean part will look at the logical conditions whilst the theory solver will look at the mathematical relationships. For example, an integer solver could be used to determine inequalities. An array solver could be used to reason about accessing and updating indexed data. These will be communicated with each other to determine if there is a valid assignment that can satisfy the logical expression along with any mathematical constraints. If there are any contradictions, they will be identified. If there is a valid combination they can return a solution.

Key Mathematical Theories Used

A key feature of an SMT solver is the ability to use different mathematical theories. These will each contain rules for reasoning about a specific type of mathematical object or computer structure. 

Which theory you use depends on the problem. If you are solving a scheduling problem you may want to use integer arithmetic and inequalities. If you are verifying software you may want to use arrays, bit-vectors and logical relationships. This means they can be used to accurately represent real world computer problems.

1. Integer and Real Arithmetic

Arithmetic theories allow an SMT solver to reason about numerical values. Integer arithmetic will look at whole numbers whilst real arithmetic will include decimals. This allows the solver to perform addition, subtraction, multiplication, division and comparisons. They can also determine if equality, greater than and less than constraints can be satisfied. 

For example, you may need to determine if a set of products can be bought without exceeding your budget of ₦100,000. The prices can be represented with numerical variables and the solver can determine if there is a combination that will satisfy the constraint. This makes them useful for financial calculations, resource allocation, engineering and scheduling.

2. Bit Vector Theory

Bit vector theories look at fixed width binary numbers. This is a key part of computer systems as information is stored in binary form on processors and digital circuits. An SMT solver can reason about addition, subtraction, AND, OR, shifting and comparisons using bit vectors. 

Unlike normal integer arithmetic, this will take into account the number of bits available. This is useful for verifying how software interacts with hardware or how the processor deals with numerical information. Developers can use this to see if arithmetic operations are behaving correctly, if values fit within their allocated space and if the software is accurately representing the hardware.

3. Array Theory

Array theory allows an SMT solver to reason about arrays. Arrays are commonly used in programming as they are a useful way of storing information. An SMT solver can determine how an array will behave when trying to access a value or update an element. 

For example, you may have an array storing customer account balances in a program. When updating one customer’s balance you may want to check that other customers balances are unchanged. Array theory provides a way of describing these operations mathematically. This is useful for software verification, databases and systems that deal with large amounts of structured information.

4. Uninterpreted Functions

Uninterpreted functions are functions that can be reasoned about without knowing how they work mathematically. The solver will just use the relationships and properties provided. For example, you may have a function called calculateScore() in a software verification problem. 

You may not need to know how it works just that the output will always be the same if the input is the same. This is useful for analysing large systems of software. Developers can use this to abstractly represent complex components. This helps to reduce the complexity of some verification problems.

5. String/Sequence Theory

String/Sequence theory allows an SMT solver to reason about text, sets of characters and ordered data. This can be useful if you have conditions to check in your software that relate to text values. Sequence theory can also be used to describe ordered sets of elements. 

Developers may want to verify that a program is correctly handling usernames, validating text inputs or dealing with sequences. These theories can be used to reason about more than just numerical problems. This makes them useful for applications involving data processing.

SAT vs SMT Solvers

Whilst SAT and SMT solvers have similar goals, there are differences in what they can represent. SAT solvers will focus on Boolean satisfiability. This makes them ideal for problems that can be represented with logical variables and clauses. SMT solvers will take this further by adding mathematical theories. This makes them ideal for more expressive problems. How complex a problem is will depend on what theories are being used and how complex the constraints are.

It is important to note that SMT solvers don’t replace SAT solvers. They build on the Boolean satisfiability methods. Many SMT solvers will use a SAT solver internally to help with the Boolean aspects. They will then use individual theory solvers for arithmetic, arrays and more. This gives developers flexibility. If the problem is mostly Boolean they can use a SAT solver but if they need to include mathematical relationships they can use an SMT solver. Both technologies are very useful as they provide a method of determining if a complex set of requirements can be satisfied.

Real World Examples

Understanding how these solvers work can be easier by thinking about real world examples. 

Often when solving a problem in computing there will be multiple conditions to satisfy. The solver will convert these into a mathematical representation and look for a combination of values that will satisfy them.

Example 1: Boolean Logic Problem

Imagine a company is holding a training session and an employee can only attend if they have registered or have special permission. They also cannot attend if they haven’t completed their preparation. This can be represented with Boolean variables:

R = Registered

A = Approved

P = Prepared

T = Can attend

This can be written as:

T = (R OR A) AND P

The SAT solver will look at the possible combinations of values. In this case if the employee has registered and prepared the expression will be true. If they have special permission and are prepared they can also attend. However if they have only registered or been approved they can’t attend as they haven’t prepared. This is a simple example showing how a SAT solver can look at multiple conditions to find the valid decisions. Larger systems can use the same techniques to look at hundreds or thousands of Boolean variables.

Example 2: Scheduling Problem

Imagine if a University needs to schedule three exams and don’t want students taking multiple subjects to have overlapping exam times. Each exam will need to be scheduled at a specific time. Variables can be used to represent the time each exam is scheduled for. The solver will be given constraints that the exams cannot be scheduled at the same time for students taking them and that they need to be scheduled at an available time. If there is a limit on how many people can fit in a room this can also be included in the mathematical representation.

An SMT solver can look at the time and numerical constraints to find a valid solution. For example, if Mathematics needs to be finished before Physics starts this can be represented as an inequality. The solver can then combine this with other constraints to find a suitable solution. If the constraints cannot all be satisfied the solver will tell you there is no valid solution. This can be useful in education, business, transport systems and organisations that need to schedule lots of activities.

Example 3: Mathematical Constraints

Imagine if a delivery company needs to determine if a vehicle can complete a journey within a time frame. The vehicle needs to go to multiple locations and each section of the journey has a known distance and estimated time. There are also constraints including fuel capacity, deadlines for deliveries and maximum distance the vehicle can travel. These can all be represented with mathematical variables and inequalities. An SMT solver can look at the relationships between the variables to determine if there is a combination that can satisfy all the constraints.

For example, the solver may be told the journey cannot take longer than 5 hours and the distance travelled cannot exceed the vehicle’s range. They may also want to know if each delivery is completed on time. If there is a suitable combination of routes and arrival times the solver can return values that satisfy the constraints. If there is a contradiction they can identify the problem as being unsatisfiable. This shows how an SMT solver can be used to reason about numerical relationships. They can be useful for managing resources, transport and optimisation.

Major Uses of SAT and SMT Solvers

SAT and SMT solvers have become an important tool in many areas of computer science and engineering. They can be used to look at complex logical and mathematical relationships. 

This can be useful for any system that needs to know if a set of requirements can be satisfied. Developers can use automated reasoning to look at possible outcomes, identify contradictions and verify if systems meet their requirements.

1. Software Testing and Verification

A key application of SAT and SMT solvers is in software testing. Many software applications include a huge amount of conditions, branching and variables that need to be considered. Using SAT and SMT solvers, developers can find out if there are certain inputs that make certain parts of the code run by analysing the conditions within the program. This is often referred to as symbolic execution.

An application may include conditions that determine if a transaction goes through. There may be many conditions that need to be met including account balances, transaction limits, user permissions and other requirements. Using an SMT solver, developers can see what mathematical and logical conditions need to be met to determine if an input satisfies a certain path. This can help create test cases using the values given. This can help identify logical errors and unexpected conditions within the software. This also helps increase test coverage by allowing developers to understand different paths.

2. Hardware Design and Verification

SAT and SMT solvers are important tools within digital hardware design. Many modern processors, memories, communication and circuits contain millions of components. Engineers need to ensure that these are working as intended. If there is a small logical error then this may impact the reliability of the whole electronic system. Using SAT verification tools engineers can create Boolean expressions to see if certain combinations of inputs can cause unexpected outputs.

When designing a processor engineers may need to ensure that a certain instruction works as intended. Using a SAT Solver engineers can find out if there is an invalid output by looking at the logical representation of the circuit. If the verification requires fixed width arithmetic or other maths an SMT solver can be used. This is a valuable tool as often during hardware verification there are a large number of input combinations to consider. Using these technologies can help engineers see any issues within the design.

3. Cybersecurity and Finding Vulnerabilities

Automated reasoning is used within cybersecurity to understand how a piece of software behaves. This can help identify any security issues and find out if there are any conditions that could leave a system vulnerable. Many complex applications will have a variety of permissions, authentications, data processing and access restrictions. This can make it hard to determine if they are working correctly. Using SAT and SMT solvers engineers can create mathematical representations of these conditions to determine if any unintended combinations are possible.

Developers may want to ensure that a certain function cannot be accessed by a user who does not have the right permissions. This can be done by creating logical constraints around the access. A SAT solver can be used to find out if there is a chance of an invalid output. If the verification requires fixed width arithmetic or other maths then an SMT solver can be used. These technologies are very valuable as there are often lots of input combinations to consider. Using these tools can help engineers find any issues within the design.

4. Artificial Intelligence and Automated Reasoning

Many AI systems will need to make decisions based on a variety of conditions. Whilst machine learning focuses on pattern recognition, SAT and SMT solvers can help systems make logical decisions. This can help with any AI systems that need to follow strict rules.

An intelligent planning system may need to allocate resources to certain activities taking into consideration time, cost, availability and priority. An SMT solver can create a representation of these requirements and find a valid allocation. In rule based AI a SAT solver can help determine if a set of logical statements can be used to come to a certain conclusion. These technologies can be used with machine learning to provide constraint based reasoning. This can be very useful for any applications that need to follow strict requirements.

5. Scheduling

Many scheduling problems will have a variety of tasks to complete with limited resources. An organisation may need to allocate staff to shifts, classrooms to courses, transport times and equipment to projects. This can become very complex if there are multiple activities that depend on each other. Using SAT and SMT solvers can help create a representation of these requirements.

A hospital may need to allocate staff to different shifts to ensure there is enough cover within each department. An SMT solver can create logical and mathematical representations of staff availability, duration of shift, staff requirements and scheduling constraints. This can be used to find a valid combination. If there is a valid combination then the solver will return an assignment. However this does not always give the best combination. Other optimisation techniques may be needed if an organisation wants to reduce costs, balance workload or utilise resources.

6. Automated Planning

Automated planning is used to find out the actions required to take a system from an initial state to a desired goal. This is often used in robotics, logistics, intelligent systems and other applications. Each action may have certain requirements that need to be met. SAT and SMT solvers can create a representation of these requirements.

A warehouse management system may need to move products from storage to a certain location. This needs to take into consideration equipment available, movement restrictions, product location and prioritise deliveries. An SMT solver can create a representation of actions and conditions to determine if the objectives can be met. These techniques can also help with robots, logistics and industrial processes. This can help automated systems make decisions based on the relationships.

Popular SAT and SMT Solving Tools

There are many tools that have been developed to help with SAT and SMT solving. Depending on the type of problem being solved different algorithms and programming languages will be available to use. 

Some are focused around Boolean satisfiability whilst others can handle multiple mathematical theories.

1. MiniSat

MiniSat is a popular SAT solver. It solves Boolean satisfiability problems. This is an important tool in computer science research and education as it provides an easy to use version of modern SAT solving techniques. It uses conflict driven clause learning to increase performance. 

Researchers can use this to look into satisfiability problems. It can be used to experiment with solving techniques and understand how modern SAT solvers work. It has a simple design and so can be useful for learning purposes and developing further SAT solvers.

2. Z3

Z3 is a powerful SMT solver developed by Microsoft Research. It can handle multiple theories including arithmetic, bit vectors, arrays and uninterpreted functions. This makes it useful for software verification, symbolic execution, program analysis and automated reasoning. 

There are multiple programming languages that can be used to interact with Z3. This can be used to create complex constraints including both Boolean and mathematical conditions. A developer can use this to see if a certain condition can be met within their program or if there is a valid solution to a set of numeric constraints.

3. CVC5

CVC5 is an open source SMT solver that can handle a wide variety of satisfiability problems. It can handle arithmetic, array, bit vector, string and other structured expressions. Researchers can use this to look into automated reasoning. Developers can use it within their applications to solve mathematical constraints. 

It can handle multiple theories making it useful for analysing complex systems. This can be useful for research into formal verification and creating more advanced automated reasoning systems.

4. Kissat

Kissat is a modern SAT solver that can handle large Boolean satisfiability problems. It includes advanced search techniques to help with solving complex sets of clauses. It has been used in SAT competitions. 

This shows how the improvements to algorithms and techniques have helped increase performance. Whilst it does not handle multiple mathematical theories like SMT solvers it does help with Boolean satisfiability problems.

Advantages of using SAT and SMT Solvers

One main advantage of using SAT and SMT solvers is they can help automate complex reasoning problems. Many problems can become very complex with multiple conditions linked together. Changing one variable may affect multiple other conditions. SAT and SMT solvers can help identify if there is a satisfying assignment by looking into the relationships. This can reduce the amount of work that a developer has to do to analyse complex logical and mathematical problems. It can also help developers understand complex scenarios with many possible combinations.

Another advantage is they can help improve reliability of software and hardware. Developers can use SAT and SMT solvers to check if a system meets certain requirements and if there are any errors or unexpected behaviour that can occur. This can save costs during development by identifying any issues early. They can also be used for a variety of different representations. SAT solvers can be used for Boolean relationships whilst SMT solvers can be used for mathematical theories. They can be used for many applications including software engineering, cybersecurity, AI and hardware design making them an important tool.

Disadvantages of using SAT and SMT Solvers

One main disadvantage of using SAT and SMT solvers is the complexity of solving the problems. SAT is an NP-Complete problem and there is no known algorithm that can solve all SAT problems efficiently. Whilst modern solvers can solve many problems very well there are some expressions that can be very complex to solve. As there are more Boolean variables there are a large number of possible assignments. SMT problems can become more complex as they also have to reason about the mathematical theories. This means that the performance will depend on the problem structure, theories chosen and algorithms implemented.

Another disadvantage is they can only solve the conditions they are given. If a developer gets the conditions wrong then the solver may return a mathematically correct answer but that does not fit with the real world scenario. For example if a scheduling model does not account for an important staff availability condition then it may return an assignment that looks valid but cannot be implemented. Developers will need to fully understand the problem and ensure that the conditions are accurately represented in logical and mathematical constraints. This means that the outcome will depend on how accurate the modelling is.

Some problems may be very large with complex mathematical conditions and many conditions to consider. Certain theories can be harder to solve than others and some combinations can be very intensive. This may mean that there is a large increase in memory usage and processing time. The solvers do not always return the best solution. A satisfying assignment will just tell you that the conditions provided can be met. If the aim is to reduce costs, processing time or increase efficiency then further optimisation may be needed. This is why SAT and SMT solvers are often used with other software engineering and optimisation techniques.

The Future of SAT and SMT Solving

SAT and SMT Solving is still evolving as computer systems become more complex. Improvements to search algorithms, conflict analysis, mathematical theories and solver architecture are helping researchers solve more complex problems. As software applications become more interlinked developers need reliable ways to see how different components interact and if they meet the required specifications. SAT and SMT solvers are likely to still be important as they can provide mathematical solutions for analysing complex system behaviour.

Another important development is the relationship between automated reasoning and AI. Machine learning systems can identify patterns and make predictions but do not always provide outputs that will meet strict logical conditions. Constraint solvers can be used with these systems to check if certain decisions meet certain rules and conditions. For example an AI planning application can create a possible resource allocation and an SMT solver can check if this meets time, capacity and availability conditions. This could help create more reliable decisions in areas such as transport, industrial automation, robotics and intelligent software development.

As formal verification is becoming more popular this will help increase the use of SAT and SMT technologies. With organisations relying on software for financial services, healthcare, communications, transport and other important activities it is becoming increasingly valuable to ensure systems are working as intended. Automated reasoning can help developers understand complex conditions, identify inconsistencies and confirm important properties of a system. Whilst they cannot completely remove all defects within software they can help analyse complex logical and mathematical conditions making them a valuable part of modern software engineering.

Conclusion

SAT and SMT solvers are an essential technology for automated reasoning. They allow computers to determine if complex sets of logical and mathematical conditions can be met. SAT solvers work with Boolean expressions to determine if there are any valid assignments of truth values. SMT solvers build upon this by including mathematical theories such as integer arithmetic, real arithmetic, bit vectors, arrays and uninterpreted functions. This provides a powerful way to represent and analyse problems with many interlinked conditions. They can help eliminate any inconsistent possibilities and find satisfying assignments. This can help with many complex computational problems.

They can be used in many areas including software testing, hardware verification, cybersecurity, AI, scheduling and automated planning. Tools such as MiniSat, Z3, CVC5 and Kissat can show how automated reasoning can be used in development and research. Despite challenges such as complexity, scalability and incorrect modelling the improvements are making them very effective. As computer systems become more advanced SAT and SMT solvers will continue to help create reliable software, hardware that works correctly and intelligent systems that can make decisions whilst considering complex logical and mathematical conditions.