2.14. Reduction of SAT to 3-SAT¶
2.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.
This reduction can help in providing an NP Completeness proof for 3-SAT.
