.. 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: Cliff Shaffer and Mostafa Mohammed
   :topic: NP-completeness
   :keyword: NP-completeness


NP-Completeness
===============

Hard Problems
-------------

.. inlineav:: TravelSalesmanFS ff
   :links: AV/PIFLA/LimComp/TravelSalesmanFS.css
   :scripts: DataStructures/PIFrames.js AV/PIFLA/LimComp/TravelSalesmanFS.js
   :output: show
   :keyword: NP-completeness

|

.. inlineav:: KCliqueFS ff
   :links: AV/PIFLA/LimComp/KCliqueFS.css
   :scripts: DataStructures/PIFrames.js AV/PIFLA/LimComp/KCliqueFS.js
   :output: show
   :keyword: NP-completeness


Proving that a Problem is NP-Complete
-------------------------------------

.. inlineav:: SATProofFS ff
   :links: AV/PIFLA/LimComp/SATProofFS.css
   :scripts: DataStructures/PIFrames.js AV/PIFLA/LimComp/SATProofFS.js
   :output: show
   :keyword: NP-completeness


Coping with NP-Complete Problems
--------------------------------

.. inlineav:: NPCCopingFS ff
   :links: AV/PIFLA/LimComp/NPCCopingFS.css
   :scripts: DataStructures/PIFrames.js AV/PIFLA/LimComp/NPCCopingFS.js
   :output: show
   :keyword: NP-completeness