Data Structures and Algorithms

Chapter 11 Limits to Computing (optional)

Show Source | | About « 11.3. NP-Completeness (optional) (WORK IN PROGRESS) :: Contents :: 11.5. Formula Satisfiability (optional) (WORK IN PROGRESS) »

11.4. Circuit Satisfiability (optional) (WORK IN PROGRESS)¶

11.4.1. Circuit Satisfiability¶

Settings

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.

Contact Us || Privacy | | License « 11.3. NP-Completeness (optional) (WORK IN PROGRESS) :: Contents :: 11.5. Formula Satisfiability (optional) (WORK IN PROGRESS) »