Close
Register
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.

Settings

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