В теории сложности проблема выполнимости (SAT) - это проблема принятия решения, экземпляр которой представляет собой логическое выражение, записанное с использованием только AND, OR, NOT, переменных и круглых скобок.
Проблема булевой выполнимости - это своего рода проблема.