Information Technology Reference
In-Depth Information
of accepting paths of
M
and the number of rejecting paths of
M
, respectively, on
input
x
.
GapL is a function class andwe have an appropriate notion of logspace computable
reductions for this class. Given two functions
f
, g
:
ˇ
∗
ₒ Z
we say that
f
is
m
g
) if there are two logspace
logspacemany-one reducible to
g
(as usual, denoted
f
≤
∈
ˇ
∗
computable functions
e
and
v
such that for every
x
f
(
x
)
=
v(g(
e
(
x
))).
Notice that if
g
is computable in logspace then
f
is also logspace computable.
A function
g
∈
m
g
for every
GapL isGapL-
complete
under logspace reductions if
f
≤
f
GapL. A fundamental result due Toda [
Tod91
] is that the integer determinant is
GapL-complete. The result has an elegant proof by Mahajan and Vinay [
MV97
]. A
problem analogous to REACH that is easily shown to be GapL-complete is in the
following exercise.
∈
Exercise
Given a directed acyclic graph
G
with a source vertex
s
and two sink
vertices
t
1
and
t
2
,let
g(
denote the difference of the number of directed
paths from
s
to
t
1
from the number of directed paths from
s
to
t
2
. Show that this
function is GapL-complete.
G
,
s
,
t
1
,
t
2
)
The class GapL is analogous to the complexity class #P [
Va l 7 9
] introduced by
Valiant to study the complexity of computing the integer permanent. A function
f
:
ˇ
∗
ₒ N
(
)
=
acc
M
(
)
is said to be in #P if there is an NP machine
M
such that
f
x
x
∈
ˇ
∗
. A celebrated result due to Valiant [
Va l 7 9
] is the #P-completeness of
the integer permanent (for an appropriate notion of reductions). The reader can find
details of the proof in the textbook [
AB09
].
for all
x
Remark 7.2
As an aside, comparing the computational complexity of the determi-
nant and the permanent is a fascinating topic that is central to the area of arithmetic
circuits. This topic includes several chapters on the topic of arithmetic circuits. Meena
Mahajan's article presents a detailed survey onValiant's algebraic complexity classes.
The complexity of computing the determinant of matrices over the field
F
2
is
captured by the language class
↕
L defined below.
ↆ
ˇ
∗
is in the complexity class
Definition 7.3
A language
L
L (called “parity-
L”) if there is a logspace bounded nondeterministic Turing machine
M
such that
x
↕
∈
L
⃒⃐
acc
M
(
x
)
is odd.
Exercise
Show that the following language is
↕
L complete under logspace many-
one reductions:
ODD
−
REACH
={
G
,
s
,
t
|
G
is a DAG such that there is an odd number
of directed paths from
s
to
t
}
.
