Boolean Satisfiability Problem (SAT)

SAT is the first problem proven to be NP-complete (Cook-Levin Theorem, 1971). This means:

• Any problem in NP (nondeterministic polynomial time) can be reduced to SAT in polynomial time.
• A polynomial-time algorithm for SAT would imply P = NP, solving one of the most famous open questions in computer science.
• Its completeness makes SAT a universal tool; solving hard optimization, scheduling, or verification problems often involves encoding them as a SAT instance for a solver.

While SAT applies to any Boolean formula, it is standardly presented in Conjunctive Normal Form (CNF), a conjunction (AND) of clauses, where each clause is a disjunction (OR) of literals (variables or their negations).

• Example: (x1 OR ¬x2) AND (¬x1 OR x3) AND (x2)
• This standardized input format, while seemingly restrictive, is expressively complete and allows for highly optimized solver algorithms like Conflict-Driven Clause Learning (CDCL).
• The k-SAT sub-problem, where each clause has exactly k literals, is a common benchmark (e.g., 3-SAT remains NP-complete).

For a formula with n Boolean variables, the naive search space size is 2^n (all possible truth assignments).

• SAT solvers do not brute-force this space. They employ sophisticated proof systems like Resolution. A solver's execution trace of conflicts and learned clauses constitutes a resolution proof that the formula is unsatisfiable.
• The Pigeonhole Principle formulas are classic examples that are trivially unsatisfiable but require exponential-size resolution proofs, illustrating the theoretical limits of certain solver strategies.

Randomly generated SAT instances exhibit a sharp phase transition in solubility based on the clause-to-variable ratio.

• Below a critical ratio (≈4.26 for 3-SAT), problems are almost always satisfiable (underconstrained).
• Above it, they are almost always unsatisfiable (overconstrained).
• Hardest instances for solvers occur at this phase transition boundary, where the search tree is maximally balanced. This phenomenon is crucial for benchmarking solver performance.

A critical distinction in logic and automated reasoning:

• Satisfiability (SAT): Is there some assignment of variables that makes the formula TRUE? This is the core decision problem.
• Validity (TAUTOLOGY): Does the formula evaluate to TRUE under all possible assignments?
• The two are duals: A formula F is valid if and only if ¬F is unsatisfiable. This duality is exploited in model checking and theorem proving, where proving a property always holds (validity) is done by showing its negation can never be satisfied.

A Constraint Satisfaction Problem (CSP) is a formal framework for modeling combinatorial problems. It is defined by:

• A set of variables, each with a domain of possible values.
• A set of constraints that specify allowable combinations of values for subsets of variables.

SAT is a specific type of CSP where variables are Boolean (True/False) and constraints are expressed as clauses in a Boolean formula. General CSPs extend this to variables with arbitrary finite domains (e.g., colors, time slots, integers) and a wider variety of constraint types, forming the basis for scheduling, configuration, and routing agents.

Satisfiability Modulo Theories (SMT) is a generalization of SAT that determines the satisfiability of logical formulas with respect to background theories. While SAT solvers work with pure Boolean logic, SMT solvers integrate specialized theory solvers for domains like:

• Linear integer arithmetic (e.g., x + 2*y < 10)
• Bit-vectors (for hardware verification)
• Uninterpreted functions and arrays

This allows SMT to express and solve complex constraints that arise in software verification, program analysis, and hybrid systems, making it a more expressive tool for agentic reasoning about real-world properties.

Conflict-Driven Clause Learning (CDCL) is the dominant algorithmic architecture powering modern SAT solvers. It enhances basic backtracking search with two key mechanisms:

• Clause Learning: When a conflict (a dead-end) is reached, the solver analyzes the reason for the conflict and derives a new clause (a constraint) that prevents the same erroneous assignment from being explored again.
• Non-chronological Backtracking: Instead of backtracking one step, the solver uses the learned clause to jump back to the decision level that caused the conflict.

This combination allows CDCL solvers to efficiently navigate massive search spaces, making practical solutions to large industrial SAT instances possible.

A Constraint Optimization Problem (COP) extends a standard CSP by adding an objective function that must be maximized or minimized. The goal is no longer to find any feasible solution, but to find the best feasible solution according to a metric (e.g., cost, profit, distance).

Key techniques for solving COPs include:

• Integrating optimization with constraint propagation.
• Using Branch and Bound to prune search branches that cannot beat the current best solution.
• Employing local search heuristics to improve good candidate solutions.

COPs are central to enterprise agentic systems for tasks like optimal scheduling, resource allocation, and logistics planning.

Local search is a family of incomplete algorithms for CSPs that operate on a complete, but potentially invalid, assignment of values to all variables. Instead of building a solution incrementally, it starts with a full assignment and iteratively improves it.

The Min-Conflicts Heuristic is a pivotal local search strategy:

1. Select a variable that is currently violating a constraint.
2. Assign it the value that results in the minimum number of conflicts with other variables.

This approach is highly effective for large, dense CSPs like the N-Queens problem and real-time scheduling where finding a good enough solution quickly is more critical than proving optimality or exhaustive search.