SAT problem
a boolean formula is a logical expression over boolean variables (that can take values in 
) with connectives 
(standing for 
), for example, 
. let 
denote the set of all satisfiable boolean formulas (namely, those for which a boolean assignment to the variables evaluates to 1).
[cite:;taken from @computation_wigderson_2019 definition 3.12]
the SAT problem is an example of an NP-complete problem.
) with connectives (standing for ), for example, . let denote the set of all satisfiable boolean formulas (namely, those for which a boolean assignment to the variables evaluates to 1).[cite:;taken from @computation_wigderson_2019 definition 3.12]