SAT: A different kind of search problem

Overview

Kent Quanrud introduces Boolean satisfiability as a search problem: a satisfying assignment is easy to verify, but brute force over n variables may require checking 2^n assignments. He shows how polynomial-size reductions using auxiliary variables turn arbitrary Boolean formulas into CNF and 3-SAT, and extend the same idea to circuit SAT—establishing that these problems are equivalent with respect to having polynomial-time algorithms, not that such an algorithm is known.

Key takeaways

A satisfying assignment for a Boolean formula is easy to verify by evaluating the formula, but the generic search method checks up to 2^n assignments for n variables.
Distributing nested ANDs and ORs into CNF can cause exponential growth; introducing auxiliary variables avoids duplicating subformulas.
Assigning one auxiliary variable to each gate and encoding its local input-output relationship yields a satisfiability-preserving CNF instance whose size is linear in the number of formula gates.
Binary-gate encodings produce clauses with at most three literals, and a two-literal clause C can be padded to exactly three using (C OR y) AND (C OR NOT y).
The gate-by-gate reduction works for circuits as well as formula trees because a DAG’s shared intermediate nodes can keep one variable instead of being expanded repeatedly.
Polynomial-time solvability of general Boolean SAT, CNF SAT, 3-SAT, and circuit SAT is linked by reductions; these reductions establish equivalence of the algorithmic questions, not a proof that no polynomial-time solver exists.

Chapters

0:00 Boolean Formulas Express XOR, Equality, and If-Else Logic

XOR can be written as (x AND NOT y) OR (NOT x AND y), listing the two input combinations that produce true.
Equality between z and x is (z AND x) OR (NOT z AND NOT x), derived by identifying the true rows of its truth table.
A conditional that returns y when x is true and z otherwise is (x AND y) OR (NOT x AND z).
These examples show how AND, OR, and NOT can encode basic programming operations such as assignment and branching.

7:00 SAT Searches for an Assignment That Makes a Formula True

Boolean satisfiability asks whether any assignment to variables x1 through xn makes a given formula evaluate to true.
Quanrud illustrates an unsatisfiable formula over two variables by covering all four possible assignments with clauses that each rule one out.
A proposed satisfying assignment is easy to verify by evaluating the formula, even when finding one may be difficult.
Checking all 2^n assignments is a general brute-force method, but it is not polynomial-time in the number of variables.

11:00 Why SAT Resists Obvious Search and Dynamic Programming

The central algorithmic question is whether Boolean SAT can be solved in polynomial time rather than by enumerating 2^n inputs.
Nested AND and OR operators create branching choices: an OR can let a formula bypass an entire AND-constrained branch.
A dynamic program needs a compact, reusable description of subproblems; after variable choices, the remaining clauses may form an irregular collection.
Naively flattening nested formulas with distributive laws can duplicate subexpressions and produce an exponentially larger formula.

18:00 Conjunctive Normal Form: An AND of OR Clauses

Conjunctive normal form (CNF) consists of an AND at the root combining OR clauses, rather than an arbitrarily nested Boolean tree.
This flat structure looks more tractable, but Quanrud emphasizes that it is still expressive enough to warrant caution about assuming an efficient solver.
A proposed dynamic program over variables must account for how each assignment affects many clauses, not merely track a simple interval or subsequence.

22:00 Distributing Boolean Formulas into CNF Can Cause Blowup

Quanrud converts small formulas such as z = x and an if-else expression into CNF using distributive laws and tautological clauses.
For example, z = x can be expressed as the two clauses (z OR NOT x) AND (x OR NOT z).
Mechanical distribution works on small examples, but repeated expansion can multiply clause counts and grow exponentially with nesting.
The examples motivate a different conversion method that avoids expanding every combination of ANDs and ORs.

32:00 CNF SAT and General Boolean SAT Share the Same Polynomial-Time Prospects

CNF SAT is a special case of Boolean SAT, so a polynomial-time solver for general Boolean formulas would immediately solve CNF instances.
The more surprising direction is to transform every Boolean formula into a CNF formula of polynomial size.
If that transformation exists, a polynomial-time CNF SAT solver could serve as a black box for general SAT.
This reduction perspective explains why a seemingly simpler special case can be as demanding as the general problem.

34:00 Use a Polynomial-Time Reduction Instead of Expanding the Formula

The reduction must convert an input formula in polynomial time and keep the resulting CNF size polynomial in the original input size.
A direct De Morgan and distribution approach can create exponentially many clauses, so it fails the size requirement.
The conversion is allowed to introduce new variables; the important constraint is that the full encoded instance remains polynomial in size.

37:00 Auxiliary Variables Encode Each Boolean Gate Locally

Quanrud assigns a fresh variable, such as z1, to an internal subformula such as x1 AND x2, then uses z1 in the surrounding formula.
Each local relationship between a gate output and its inputs can be expressed with a small CNF gadget.
For z1 = x2 AND x3, the encoding uses clauses that enforce both directions of the equivalence, rather than merely one implication.
Replacing subtrees with named variables prevents the repeated duplication that makes direct distribution blow up.

42:00 Gate-by-Gate Encoding Keeps CNF Clauses Small

After converting the formula tree to binary gates, each internal node receives an auxiliary variable and a constant-size group of clauses.
The lecture works through local encodings for AND and OR gates using De Morgan’s law and Boolean equivalences.
The complete CNF combines the local gate constraints and requires the variable representing the formula’s output to be true.
Binary gates ensure each encoding clause contains at most three literals, setting up a direct reduction to 3-SAT.

47:00 The CNF Encoding Is Linear-Size and Preserves Satisfiability

Each original internal node contributes only a constant number of symbols and clauses, so a formula with m nodes yields a CNF encoding of O(m) size.
If the original formula is satisfiable, assigning each auxiliary variable the value of its subformula satisfies the gate constraints.
Conversely, any satisfying assignment to the CNF must give the auxiliary variables values consistent with the gates, yielding a satisfying assignment for the original formula.
A polynomial-time CNF SAT solver could therefore solve general Boolean SAT by first applying this encoding.

52:00 Reducing CNF SAT to 3-SAT with Dummy Variables

3-SAT restricts CNF clauses to at most three literals; the binary-gate construction already produces clauses of this size.
To turn a two-literal clause C into clauses of exactly three literals, introduce y and replace it with (C OR y) AND (C OR NOT y).
The two padded clauses together are satisfiable exactly when the original clause C is satisfied, regardless of y’s value.
Thus Boolean SAT, CNF SAT, and 3-SAT can be related through polynomial-size, satisfiability-preserving reductions.

59:00 Circuit SAT Allows Shared Subcomputations in a DAG

A Boolean circuit is a directed acyclic graph (DAG), unlike a formula tree, because multiple gates can reuse the same intermediate result.
Circuit SAT asks whether some input assignment makes the circuit’s output true.
The same auxiliary-variable technique assigns a variable to each gate and adds local clauses describing its operation.
Shared nodes do not require expanding the circuit into a tree, so the gate-by-gate CNF encoding remains polynomial in circuit size.

1:05:00 SAT Reductions Frame the Coming Study of Complexity Theory

Circuit SAT can be reduced to CNF SAT and then to 3-SAT, while formulas and 3-SAT instances can also be viewed as circuits.
These reductions show that finding a polynomial-time algorithm for any one of the problems would yield one for the others.
Quanrud does not prove that SAT lacks a polynomial-time algorithm; the result is an equivalence of algorithmic prospects among the problems.
The lecture introduces complexity theory as the study of why some problems appear solvable by regular algorithms while others resist them.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.