CoreSource checked

Unit Propagation

Simplifies SAT formulas by repeatedly assigning literals forced by unit clauses.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Optimization
Difficulty: Intermediate
Family: SAT Solving
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 5
Code example: Ready
Visualization: Ready

Overview

Unit propagation finds clauses with only one unassigned literal and assigns that literal so the clause becomes true, repeating until no unit clauses remain or a conflict appears.

Core Concepts

satisfiability simplificationsat solvingunit propagationoptimization

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(2^n)

Worst

O(2^n)

Space

O(2^n)

When to Use

Use inside SAT solvers whenever partial assignments can force additional variables.
Use when early contradiction detection can prune a search branch.

When Not to Use

Avoid treating propagation alone as a complete SAT solver.
Avoid when clause and assignment data structures cannot be updated consistently.

What It Does

Unit Propagation uses forcing assignments implied by clauses with only one unassigned literal for satisfiability simplification
Organizes the work around satisfiability simplification and sat solving.

Use Cases

Production and research workloads requiring sat solving via Simplifies SAT formulas by repeatedly assigning literals forced by unit clauses.
SAT Solving pipelines where O(2^n) time and O(2^n) space fit system constraints.
Engineering comparisons against DPLL and CDCL when tuning sat solving.

Inputs

Objective, constraints, and candidate variables
Problem-specific costs or feasibility rules

Outputs

Best known feasible solution
Optimality or approximation result when available

Key Formulas (1)

Unit clause rule

(l) forces l = true

(l) forces l = true

A clause with one unassigned literal forces that literal's truth value.

Pseudocode

1.Initialize a queue with all unit clauses
2.While the queue is not empty
3.Assign the unit literal if unassigned
4.If the opposite assignment already exists, report conflict
5.Update affected clauses and enqueue new unit clauses
6.Return the implied assignments

Canonical Example

Input: clauses (A), (!A or B), (!B or C)
Output: A=true, B=true, C=true
Explanation: Assigning A makes the second clause unit, which then forces B and C.

Implementation Notes

Use watched literals for efficient propagation in larger solvers.
Record implied assignments on a trail for undo.
Test chains of implications and immediate contradictions.

Common Pitfalls

Failing to detect an empty clause after propagation misses conflicts.
Repeatedly scanning all clauses can dominate runtime without watched literals.
Assignments must be trailed if the solver backtracks.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show forcing assignments implied by clauses with only one unassigned literal on a small satisfiability simplification example.

Step 1 of 6: Initialize a queue with all unit clauses

optimization-mechanism

Notes

Unit propagation is a simplification and pruning step; branching or learning is needed for a complete solver.

Sources (1)

What each reference supports for this entry.

Handbook of Satisfiability

Book

Reference for Unit Propagation within SAT solving, including search, simplification, learning, or local-search mechanisms.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

Alternative toCDCL

Optimization · Core