Close
Close Window

CSC215: Algorithm Design and Analysis

Chapter 16 Limits to Computing

Show Source |    | About   «  16.3. NP-Completeness   ::   Contents   ::   16.5. Formula Satisfiability  »

16.4. Circuit Satisfiability

16.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.

   «  16.3. NP-Completeness   ::   Contents   ::   16.5. Formula Satisfiability  »

Close Window