.. 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 3-SAT to Clique
   :author: Nabanita Maji
   :institution: Virginia Tech
   :topic: NP-completeness
   :keyword: NP-Completeness Proof; Satisfiability Problem; Clique Problem
   :naturallanguage: en
   :programminglanguage: N/A
   :description: Presents a reduction of an instance of the 3-Satisfiability problem to an instance of the Clique problem.

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

Reduction of 3-SAT to Clique
----------------------------

The following slideshow shows that an input instance to the **3-SAT**
problem can be reduced to an equivalent input instance to the
**CLIQUE** problem in polynomial time.
 
.. inlineav:: threeSATtoCliqueCON ss
   :links: AV/NP/threeSATtoCliqueCON.css
   :scripts: AV/NP/threeSATtoCliqueCON.js
   :output: show
   :keyword: NP-completeness; NP-completeness Proofs; Satisfiability; Clique Problem

This reduction can help in providing an NP Completeness proof for 
the Clique problem.