Close
Register
Close Window

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

28.14. Reduction of SAT to 3-SAT

28.14.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.

   «  28.13. Reduction of Circuit SAT to SAT   ::   Contents   ::   28.15. Reduction of 3-SAT to Clique  »

Close Window