.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :title: Reduction of SAT to 3-SAT
   :author: Nabanita Maji
   :institution: Virginia Tech
   :topic: NP-completeness
   :keyword: NP-Completeness Proof; Satisfiability Problem
   :naturallanguage: en
   :programminglanguage: N/A
   :description: Presents a proof that 3-CNF Satisfiability is NP-Complete, by a reduction from Satisfiability.

Reduction of SAT to 3-SAT
=========================

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.
 
.. inlineav:: SATto3SATCON ss
   :links: AV/NP/SATto3SATCON.css
   :scripts: AV/NP/SATto3SATCON.js
   :output: show
   :keyword: NP-completeness; NP-completeness Proofs; Satisfiability

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