Loading [MathJax]/jax/output/HTML-CSS/jax.js
Close
Close Window

Formal Languages With Visualizations

Chapter 11 Limits to Computing

Show Source |    | About   «  11.5. 3-CNF Satisfiability   ::   Contents   ::   11.7. The Clique Problem  »

11.6. Reduction of SAT to 3-SAT

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

1 / 51 Settings
<<<>>>


Reduction of SAT to 3-SAT

This slideshow shows how to convert (reduce) a general instance of the Formula Satisfiability problem to a version with exactly 3 literals in every clause (so as to be a valid input to the 3-CNF Satisfiability problem) in polynomial time
Proficient Saving... Error Saving
Server Error
Resubmit

This reduction can help in providing an NP Completeness proof for 3-SAT.

   «  11.5. 3-CNF Satisfiability   ::   Contents   ::   11.7. The Clique Problem  »

nsf
Close Window