.. _threeSAT_to_clique:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "threeSAT_to_clique";ODSA.SETTINGS.MODULE_LONG_NAME = "Reduction of 3-SAT to Clique problem.";ODSA.SETTINGS.MODULE_CHAPTER = "Limits to Computing"; ODSA.SETTINGS.BUILD_DATE = "2016-11-25 11:27:02"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:


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

.. avmetadata::
   :author: Nabanita Maji
   :topic: NP-completeness

.. odsalink:: AV/Development/NP/threeSATtoCliqueCON.css

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

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

The following slideshow shows that an instance of 3-CNF Satisfiability 
problem can be reduced to an instance of Clique problem in 
polynomial time.
 
.. inlineav:: threeSATtoCliqueCON ss
   :output: show

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

.. odsascript:: AV/Development/NP/threeSATtoCliqueCON.js