Everything About ___
Live briefing

Everything about Boolean satisfiability problem

Problem of determining if a Boolean formula could be made true

In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the formula's variables can be consistently replaced by the values TRUE or FALSE to make the formula evaluate to TRUE. If this is the case, the formula is called satisfiable, else unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable. Wikipedia →

🧭 Start here: a 6-step reading path

  1. Read the overview: Boolean satisfiability problemA 5-minute orientation
  2. Skim a recent paper: Solving Boolean Satisfiability Problems With The Quantum Approximate Optimization AlgorithmInfluential work since 2022
  3. Pick up a classic book: Introduction to automata theory, languages, and computationThe most-reprinted book on the subject
  4. Read the landmark paper: On the Structure of the Boolean Satisfiability Problem: A SurveyCited 29 times
  5. Go sideways: XOR-SATA closely related topic
  6. Go sideways: MAXEkSATA closely related topic

📖 Definitions

No dictionary entry for this exact phrase.

🗂️ The subject at a glance

  1. Definitions
  2. Complexity
  3. Special instances of 3SAT
  4. Not 3SAT problems
  5. Schaefer's dichotomy theorem
  6. Extensions of SAT
  7. Finding a satisfying assignment
  8. Algorithms for solving SAT

🏆 Landmark papers (most cited)

🆕 Influential since 2022

📚 Books worth reading

Ranked by number of editions on Open Library, a rough measure of how lasting a book is.

🔗 Related topics