Information Technology Reference
In-Depth Information
Input
Gates
Ty p e
TRUE
FALSE
NOT
AND
OR
x
i
=
1
x
i
=
0
w
=
¬
u
w
=
u
∧
v
w
=
u
∨
v
Function
Inequalities
x
i
=
1
x
i
=
0
0
≤
w
≤
1
0
≤
w
≤
1
0
≤
w
≤
1
w
=
1
−
u
w
≤
u
u
≤
w
w
≤
v
v
≤
w
u
+
v
−
1
≤
w
w
≤
u
+
v
Given an instance of
CIRCUIT VALUE
, each assignment to a variable is translated into
an equality statement of the form
x
i
=
0or
x
i
=
1. Similarly, each
AND
,
OR
,and
NOT
gate is translated into a set of inequalities of the form shown above. Logarithmic temporary
space suffices to hold gate numbers and to write these inequalities because the number of
bits needed to represent each gate number is logarithmic in the length of an instance of
CIRCUIT VALUE
.
To see that an instance of
CIRCUIT VALUE
is a “Yes” instance if and only if the instance
of
LINEAR INEQUALITIES
is also a “Yes” instance, observe that inputs of 0 or 1 to a gate
result in the correct output if and only if the corresponding set of inequalities forces the
output variable to have the same value. By induction on the size of the circuit instance, the
values computed by each gate are exactly the same as the values of the corresponding output
variables in the set of inequalities.
We give as our last example of a
P
-complete problem
DTM ACCEPTANCE
, the problem
of deciding if a string is accepted by a deterministic Turing machine in a number of steps
specified as a unary number. (The integer
k
is represented as a unary number by a string of
k
characters.) For this problem it is more convenient to give a direct reduction from all problems
in
P
to
DTM ACCEPTANCE
.
DTM ACCEPTANCE
Instance:
A description of a DTM
M
,astring
w
,andaninteger
n
writteninunary.
Answer:
“Yes” if and only if
M
,whenstartedwithinput
w
, halts with the answer “Yes” in
at most
n
steps.
THEOREM
8.9.3
DTM ACCEPTANCE
is
P
-complete.
Proof
To s h ow t h a t
DTM ACCEPTANCE
is log-space complete for
P
, consider an arbitrary
problem
P
in
P
and an arbitrary instance of
P
,namely
x
. There is some Turing machine,
say
M
P
, that accepts instances
x
of
of length
n
in time
p
(
n
)
,
p
a polynomial. We assume
that
p
is included with the specification of
M
P
. For example, if
p
(
y
)=
2
y
4
+
3
y
2
+
1, we
can represent it with the string
((
2, 4
)
,
(
3, 2
)
,
(
1, 0
))
. The log-space Turing machine that
translates
M
P
and
x
into an instance of
DTM ACCEPTANCE
writes the description of
M
P
together with the input
x
and the value of
p
(
n
)
in unary. Constant temporary space suffices
to move the descriptions of
M
P
and
x
to the output tape. To complete the proof we need
only show that
O
(log
n
)
temporary space suffices to write the value in
p
(
n
)
in unary, where
n
is the length of
x
.
P
Search WWH ::
Custom Search