6.8. Reduction of SAT to 3-SAT¶
6.8.1. Reduction of SAT to 3-SAT¶
The following slideshow shows that any general instance of the Formula Satisfiability (SAT) problem can be reduced to an instance of 3 CNF Satisfiability (3-SAT) problem in polynomial time.
This reduction can help in providing an NP Completeness proof for 3-SAT.
