Information Technology Reference
In-Depth Information
FAN - OUT 2 CIRCUIT SAT
Instance: A description for a circuit of fan-out 2 with free values for its input variables
and a designated output gate.
Answer: “Yes” if the output of the circuit has value 1.
Hint: To reduce the fan-out of a vertex, replace the direct connections between a gate
and its successors by a binary tree whose vertices are AND gates with their inputs con-
nected together. Show that, for each gate of fan-out more than two, such trees can be
generated by a program that runs in polynomial time.
3.36 Show that clauses given in the proof of Theorem 3.9.7 are satisfied only when their
variables have values consistent with the definition of the gate type.
3.37 A circuit with n input variables
{
x 1 , x 2 , ... , x n }
is satisfiable if there is an assignment
of values to the variables such that the output of the circuit has value 1. Assume that
the circuit has only one output and the gates are over the basis Ω=
.
a) Describe a nondeterministic procedure that accepts as input the description of a
circuit in POSE and returns 1 if the circuit is satisfiable and 0 otherwise.
b) Describe a deterministic procedure that accepts as input the description of a circuit
in POSE and returns 1 if the circuit is satisfiable and 0 otherwise. What is the
running time of this procedure when implemented on the RAM?
c) Describe an efficient (polynomial-time) deterministic procedure that accepts as in-
put the description of a circuit in SOPE and returns 1 if the circuit is satisfiable
and 0 otherwise.
d) By using Boolean algebra, we can convert a circuit from POSE to SOPE. We can
then use the result of the previous question to determine if the circuit is satisfiable.
What is the drawback of this approach?
{
AND , OR , NOT
}
CENTRAL PROCESSING UNIT
3.38 Write an assembly-language program to multiply two binary numbers using the sim-
ple CPU of Section 3.10 . How large are the integers that can be multiplied without
producing numbers that are too large to be recorded in registers?
3.39 Assume that the simple CPU of Section 3.10 is modified to address an unlimited num-
ber of memory locations. Show that it can realize any Boolean function by demonstrat-
ing that it can compute the Boolean operations AND , OR ,and NOT .
3.40 Design a circuit to produce the timing variables t j ,1
k , of the simple CPU.
They must have the property that exactly one of them has value 1 at a time and they
successively become 1.
Hint: Design a circuit that counts sequentially modulo k , an integer. That is, it incre-
ments a binary number until it reaches k , after which it resets the number to zero. See
Problem 3.13 .
3.41 Complete the design of the CPU of Section 3.10 by describing circuits for PC, MAR,
MDR, OPC, INR, and OUTR.
3.42 Show that an indirect store operation can be simulated by the computer of Section 3.10 .
j
Search WWH ::




Custom Search