SAT Problem

/sæt ˈprɒb.ləm/ · Noun · Development · Origin: 1971

Definitions

  1. The Boolean satisfiability problem: given a logical formula, determine whether there exists an assignment of true/false values to its variables that makes the whole formula true. The first problem proven NP-complete (Cook-Levin theorem).

    In plain English: Given a bunch of true/false conditions combined with AND, OR, and NOT, can you find values that make everything true at once? It's the original 'hard problem' of computer science.

    Example: "Modern SAT solvers can handle millions of variables — that's how formal verification tools check hardware designs."

Related Terms