Trying to Sidestep the SAT Problem - N J Wildberger
Offered By: Insights into Mathematics via YouTube
Course Description
Overview
Explore the SAT (Satisfiability) problem and its impact on Boolean algebra in logic gate circuit analysis. Learn about Conjunctive Normal Form (CNF) and Disjunctive Normal Form (DNF), and discover how the Algebra of Boole approach offers an alternative method for circuit analysis. Examine the concept of NP-complete problems in computer science, with the SAT problem being the first identified by Cook in 1971. Gain insights into simplifying CNF using Algebra of Boole and understand how this approach can potentially sidestep the SAT problem for smaller circuits analyzed by hand. Delve into the implications of these concepts for modern Integrated Circuit design and explore alternative ways to tackle this fundamental issue in computer science and logic.
Syllabus
Introduction
The SAT Problem ,the first NP - complete problem
Conjunctive normal form product of sums
Simplifying CNF with Algebra of Boole
Proposition
Sidestepping the SAT Problem
Taught by
Insights into Mathematics
Related Courses
Advanced Algorithms and ComplexityUniversity of California, San Diego via Coursera NP-Complete Problems
University of California, San Diego via edX Automata Theory
Stanford University via edX Razonamiento artificial
Universidad Nacional Autónoma de México via Coursera Algorithms and Data Structures
University of California, San Diego via edX