Satisfiability Problem

computation

Definition

Satisfiability Problem

The SAT problem is a decision problem that, for a given Boolean function $\Phi (\mathbf{x})$, checks whether there exists a variable assignment ${\mathbf{x}}_0$ of true and false values such that $\Phi ({\mathbf{x}}_0)$.