.. 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: Circuit Satisfiability
   :author: Nabanita Maji
   :institution: Virginia Tech
   :topic: NP-completeness
   :keyword: NP-Complete; Circuit Satisfiability Problem
   :naturallanguage: en
   :programminglanguage: N/A
   :description: Visual introduction to the Circuit Satisfiability problem.

Circuit Satisfiability
======================

Circuit Satisfiability
----------------------

.. inlineav:: circuitSATCON ss
   :long_name: Circuit Satisfiability
   :links: AV/NP/circuitSATCON.css
   :scripts: AV/NP/circuit.js AV/NP/circuitSATCON.js
   :output: show
   :keyword: NP-completeness; Circuit Satisfiability

While it is easy to check whether a given truth assignment satisfies a
given circuit,
we have no easy way of knowing whether an arbitrary cirucit has some
satisfying assignment.