Trying to sidestep the SAT problem

Insights into Mathematics

72.6K subscribers

The SAT, or Satisfiability, problem is a major issue for the Boolean algebra approach to logic gate circuit analysis. In this video we explain this central problem, and then discuss how the alternative Algebra of Boole approach to logic gates helps us to circumvent it, at least for smaller circuits that can be analysed by hand. But even for larger circuits that arise in modern Integrated Circuit design, the Algebra of Boole allows an alternative exploration of this issue.

Along the way we will talk about Conjunctive Normal Form (CNF) and also more briefly about Disjunctive Normal Form (DNF). The importance of both of these categories diminishes markedly with the Algebra of Boole orientation!

The issue of NP-complete problems in computer science is also mentioned, as the SAT problem was the first such to be identified by Cook in 1971.