Close
Close Window

CS201-OpenDSA Data Structures and Algorithms

Chapter 28 Limits to Computing

Show Source |    | About   «  28.12. NP-Completeness Proofs   ::   Contents   ::   28.14. Reduction of SAT to 3-SAT  »

28.13. Reduction of Circuit SAT to SAT

28.13.1. Reduction of Circuit SAT to SAT

The following slideshow shows that an instance of the Circuit Satisfiability problem can be reduced to an equivalent instance of the SAT problem in polynomial time.

1 / 40 Settings
<<<>>>


Reduction of Circuit SAT to SAT

Created with Raphaël 2.1.2
This slideshow presents how to reduce an input instance to the Circuit-SAT problem to an equivalent instance to the SAT problem in polynomial time.

We start by giving some background.
Proficient Saving... Error Saving
Server Error
Resubmit

This reduction can help in providing an NP Completeness proof for SAT.

   «  28.12. NP-Completeness Proofs   ::   Contents   ::   28.14. Reduction of SAT to 3-SAT  »

Close Window