Close
Close Window

CS201-OpenDSA Data Structures and Algorithms

Chapter 28 Limits to Computing

Show Source |    | About   «  28.3. NP-Completeness   ::   Contents   ::   28.5. Formula Satisfiability  »

28.4. Circuit Satisfiability

28.4.1. Circuit Satisfiability

1 / 32 Settings
<<<>>>


Introduction to Circuit Satisfiability

Created with Raphaël 2.1.2
This slideshow introduces and explains the "Circuit Satisfiability" Problem.


We start with some definitions and background.
Proficient Saving... Error Saving
Server Error
Resubmit

While it is easy to check whether a given truth assignment satisfies a given circuit, we have no easy way of knowing whether an arbitrary cirucit has some satisfying assignment.

   «  28.3. NP-Completeness   ::   Contents   ::   28.5. Formula Satisfiability  »

Close Window