16.14. Reduction of SAT to 3-SAT¶
16.14.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.
The following exercise gives you a chance to reproduce the proof that 3SAT is NP-complete. This will help to confirm whether you understand the process.
