Example of NP-complete Problem: Circuit Satisfiability

Chapter 34 1
Example of NP-complete Problem:

Circuit satisfiability
A truth assignment for a boolean combination circuit is a set of
boolean input values.
One-output boolean combinational circuit is satisfiable if it has a
satisfying assignment.
A satisfying assignment: a truth assignment that causes the
output of the circuit to be “1”
The first circuit (see example pg 989) generates “1” when
x1 = 1, x2 = 1 and x3 = 0. Thus it is satisfiable.
The second circuit is unsatisfiable. No assignment values of x1 , x2 ,
and x3 causes the circuit to produce “1” (it always produces “0”).
Chapter 34 2
The circuit satisfiability problem is,

Given a boolean combinational circuit composed of AND, OR,
and NOT gates, is it satisfiable?
Encoding: a graph-like encoding that maps any given circuit C
into a binary string < C > whose length is not much larger than
the circuit itself.
CIRCUIT-SAT = {< C >: C is a satisfiable boolean combinational
circuit}
Importance of the problem in computer-aided hardware design. If
a circuit always produces “zero” we can eliminate it
Given a circuit C we can try all input combinations to determine
whether it is satisfiable or not.
If there are k inputs, this means checking 2k configurations
(non-polynomial)
Chapter 34 3
There is a strong evidence that there is no polynomial time

algorithm for that circuit-satisfiability problem
In fact circuit-satisfiability is NP-complete
Chapter 34 4
Lemma 34.5: The circuit-satisfiability problem belongs to the

class NP
Proof:
Construct a polynomial time algorithm A, with two inputs that
can verity CIRCUIT-SAT
One input is the encoding of the circuit C and the other input is
the certificate corresponding to an assignment of the wires in C
For each gate in the circuit check that the value provided by the
certificate on the output wire is correctly computed as function of
the values on the input wires
Whenever a circuit is satisfiable, there is a certificate whose length
is polynomial in the size of C and that causes A to output “1”
Whenever a circuit is unsatisfiable, there is no certificate that can
make A believe that the circuit is satisfiable
Chapter 34 5
The second part of the proof is to show that CIRCUIT-SAT is

NP-hard. That is every language in NP is polynomial-time
reducible to CIRCUIT-SAT (property of the definition of NP
completeness)
Sketch the proof based on the workings of a computer hardware
A computer program is a sequence of instructions stored in the
computer memory
A program counter (PC) is a special memory location that points
to the instruction to be executed next.
At any point in the execution of a program, the entire state of the
computation is stored in memory
The memory also includes storage space for bookkeeping
A particular state of the computer memory is called a
configuration
Chapter 34 6
The execution of one instruction is viewed as the mapping from

one memory configuration to another memory configuration
The computer hardware that can accomplish this mapping can be
implemented as a boolean combinational circuit (denote it by M –
see figure pg 992)
Chapter 34 7
Lemma 34.6: The circuit-satisfiability problem is NP hard

Proof:
Let L be any language in NP
We will describe a polynomial-time function F computing a
function f that maps every binary string x to a circuit C = f (x)
such that x ∈ L iff C ∈ CIRCUIT-SAT
Since L ∈ N P , there must be an algorithm A that verifies L in
polynomial time
The algorithm F will use the two-input algorithm A to compute
the reduction f
Let T (n) denote the worst case running time of A on a length n
input string
T (n) = O(nk ) where k ≥ 1
Chapter 34 8
Each configuration includes, the program for A, the program

counter (PC), the auxiliary machine state, the input x, the
certificate y, and the working storage
Starting with configuration c0 , each configuration ci is mapped to
a configuration ci+1 using the combination circuit M
The output of the algorithm A (0 or 1) is written in a specific
location of the working storage when A finishes execution
If the algorithm runs at most T (n) steps, the output appears in
the working storage in cT (n)
The reduction algorithm F constructs a single combinational
circuit that generates all the configurations generated by an initial
configuration c0
The basic idea is to paste together T (n) copies of the circuit M
The output of the ith circuit is feedback to the input of the
(i + 1)st circuit
Chapter 34 9
Given an input x the algorithm F must compute a circuit

C = f (x) that is satisfiable iff there exists a certificate y such that
A(x, y) = 1
When F obtains an input x, it computes n = |x| and constructs a
combinational circuit C 0 consisting of T (n) copies of M
The input to C 0 is the initial configuration c0
The output of C 0 is the configuration cT (n)
The circuit C that computes F corresponds to a modification of
C0
The inputs of C 0 corresponding to the program for A, the initial
PC, the input x and the initial memory configuration are directly
hardwired to these known values
The only remaining input is the certificate y
All outputs to the circuit are ignored, except for the bit of cT (n)
corresponding the output of A
Chapter 34 10
The circuit C as constructed above, computes C(y) = A(x, y) for

any input y of length O(nk )
The reduction algorithm F , when provided with an input x
computes such a circuit C
We need to prove
XX1. F correctly computes a reduction function f (i.e. C is
satisfiable iff there exists a certificate y such that A(x, y) = 1)
and
XX2. F runs in polynomial time
To show (1) ==>Suppose that there exists a certificate y of
length O(nk ) such that A(x, y) = 1
If we apply the bits of y to the inputs of C, the output of
C(y) = A(x, y) = 1
Thus if a certificate exists, then C is satisfiable
==>Suppose C is satisfiable Thus there exists an input y such
Chapter 34 11
that C(y) = 1 Therefore, A(x, y) = 1

F correctly computes a reduction function
Chapter 34 12
To show (2), that is to show F runs in polynomial time Let n = |x|

The number of bits required to represent a configuration is
polynomial in n
The program A is constant in size, independent of the input x
The length of the input x is n
The length of the certificate y is O(nk )
Since the algorithm runs in at most O(nk ) steps, the amount of
working storage is at most O(nk )
We assume that this memory is contiguous
The combinational circuit M implementing the computer
hardware has polynomial size in the length of the configuration
i.e. polynomial in n
Chapter 34 13
The circuit C consists of at most t = O(nk ) copies of M , thus it

has size polynomial in n The construction of C from x can be
accomplished in polynomial time (using F ), since each step of the
construction takes polynomial time
Chapter 34 14
The language CIRCUIT-SAT is therefore at least as hard as any

language in NP, and since it belongs to NP, it is NP-complete.
Theorem 34.7: The circuit-satisfiability problem is NP-complete
Proof:
Lemmas 34.5, 34.6 and the definitions of NP-completeness.

Example of NP-complete Problem: Circuit Satisfiability

Uploaded by

Copyright:

Available Formats

Example of NP-complete Problem: Circuit Satisfiability

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Example of NP-complete Problem: Circuit Satisfiability

Uploaded by

Copyright:

Available Formats

Chapter 34 1

Example of NP-complete Problem:

The circuit satisfiability problem is,

There is a strong evidence that there is no polynomial time

Lemma 34.5: The circuit-satisfiability problem belongs to the

The second part of the proof is to show that CIRCUIT-SAT is

The execution of one instruction is viewed as the mapping from

Lemma 34.6: The circuit-satisfiability problem is NP hard

Each configuration includes, the program for A, the program

Given an input x the algorithm F must compute a circuit

The circuit C as constructed above, computes C(y) = A(x, y) for

that C(y) = 1 Therefore, A(x, y) = 1

To show (2), that is to show F runs in polynomial time Let n = |x|

The circuit C consists of at most t = O(nk ) copies of M , thus it

The language CIRCUIT-SAT is therefore at least as hard as any

You might also like