Close
Close Window

OpenDSA Stand-alone Modules

Chapter 0 modules

Show Source |    | About   «  0.219. Reduction of Circuit SAT to SAT   ::   Contents   ::   0.221. Reduction of 3-SAT to Clique  »

Reduction of SAT to 3-SAT

1. Reduction of SAT to 3-SAT

The following slideshow shows that an instance of Formula Satisfiability problem can be reduced to an instance of 3 CNF Satisfiability problem in polynomial time.

1 / 51 Settings
<<<>>>


Reduction of SAT to 3-SAT

This slideshow shows how to convert (reduce) a general instance of the Formula Satisfiability problem to a version with exactly 3 literals in every clause (so as to be a valid input to the 3-CNF Satisfiability problem) in polynomial time
Proficient Saving... Error Saving
Server Error
Resubmit

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

   «  0.219. Reduction of Circuit SAT to SAT   ::   Contents   ::   0.221. Reduction of 3-SAT to Clique  »

nsf
Close Window