wp/SAT Boolean_satisfiability_problem
The problem of determining whether the variables of a given Boolean (propositional) formula can be assigned in such a way as to make the formula evaluate to true.
It is of importance to theoretical computer science, being the first problem shown to be NP-complete. The closely related model of computation, known as a Boolean circuit, relates time complexity (of an algorithm) to circuit complexity.
a_time_leap_challenge_for_sat_solving arxiv.pdf