Close
Close Window

JMU CS327 Discrete Structures II, Spring 2019

Chapter 2 Limits to Computing

Show Source |    | About   «  2.3. NP-Completeness   ::   Contents   ::   2.5. Formula Satisfiability  »

2.4. Circuit Satisfiability

2.4.1. Circuit Satisfiability

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

In the above problem, given a particular assignment, while we can quickly check whether the assignment satisfies the circuit or not, we have no easy way of knowing whether it has any satisfying assignment.

   «  2.3. NP-Completeness   ::   Contents   ::   2.5. Formula Satisfiability  »

nsf
Close Window