.. raw:: html
.. _threeSAT_to_clique:
.. raw:: html
.. |--| unicode:: U+2013 .. en dash
.. |---| unicode:: U+2014 .. em dash, trimming surrounding whitespace
:trim:
.. odsalink:: AV/NP/threeSATtoCliqueCON.css
.. 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::
:author: Nabanita Maji
:topic: NP-completeness
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
:points: 0.0
:required: False
:threshold: 1.0
:output: show
This reduction can help in providing an NP Completeness proof for
the Clique problem.
.. odsascript:: AV/NP/threeSATtoCliqueCON.js