Advanced · Fundamentals

Boolean satisfiability problem

Visual diagram · (in preparation) · Math · (in preparation) · Worked example · 3 difficulty levels.

TL;DR. The problem of determining if a given Boolean formula can be made true by assigning TRUE or FALSE values to its variables.

Technical Definition

The problem of determining if a given Boolean formula can be made true by assigning TRUE or FALSE values to its variables.

How it works

The Boolean satisfiability problem (SAT) asks if there's an assignment of truth values (true/false) to variables that makes a logical formula true. If such an assignment exists, the formula is satisfiable; otherwise, it's unsatisfiable. SAT is a foundational problem in computer science and a key example of an NP-complete problem.

Further Reading

• Wikipedia — Glossary of AI