Information Technology Reference
In-Depth Information
∈
−ₒ
[
(
)
]≥
/
x
L
Prob
M
x
accepts
1
2
∈
−ₒ
[
(
)
]=
x
L
Prob
M
x
accepts
0
The class RL stands for randomized logspace with 1-sided error. We can analo-
gously define the more general class BPL which allows two-sided error.
Exercise
L
ↆ
RL
ↆ
NL.
An interesting point in Definition 6.1 is that we need to insist on a polynomial
time bound for the randomized machine in order to get a subclass of NL. This
is in contrast to the definitions of L and NL where the polynomial time bounds is
enforced by detecting repetition of configuration. In the case of randomized logspace
computation, allowing long computation paths can influence acceptance probabilities
in nontrivial ways. The following exercise explains this aspect.
Exercise
Show that randomized logspace machines with one-sided error (and error
probability bounded by 1
2 as in Definition 6.1) that are allowed to run for expo-
nential time accept precisely the class NL.
/
Our aim is to show that UREACH is in RL. As explained earlier it suffices to
consider undirected graphs that are
d
-regular for some constant
d
.
Let
G
be a
d
-regular graph on
n
vertices and let
A
denote its
normalized
adjacency matrix
:
A
ij
=
=
(
V
,
E
)
0 otherwise.
Since
G
is undirected, note that
A
is a real symmetric matrix. An eigenvalue of
A
is a complex number
ʻ
such that
Ax
1
/
d
if
ij
∈
E
and
A
ij
=
=
ʻ
x
for some nonzero vector
x
. Since
A
is
a symmetric matrix, by standard linear algebra [
HK71
] it follows that
A
has all real
eigenvalues. Let
ʻ
1
≥
ʻ
2
≥···≥
ʻ
n
denote its
n
eigenvalues. It is easy to see that
−
1 for all
i
.
The largest eigenvalue of
A
is 1 and an eigenvector corresponding to eigenvalue
1 is the all 1's vector. We can also think of the uniform distribution
1
≤
ʻ
i
≤
(
1
/
n
,
1
/
n
, ...,
T
on the vertex set as the eigenvector corresponding to 1.
1
/
n
)
Exercise
1. Prove that
G
has
k
connected components if and only if 1
=
ʻ
1
=
ʻ
2
=···=
ʻ
k
> ʻ
k
+
1
≥···≥
ʻ
n
, where
ʻ
1
≥
ʻ
2
≥···≥
ʻ
n
denote the
n
eigenvalues of
the normalized adjacency matrix
A
.
2. Prove that
G
is bipartite if and only if
−
1 is an eigenvalue of
A
.
As a consequence of the statements in the above exercise, if
G
is connected then
ʻ
2
<
=
ʻ
1
. Indeed, when
G
is connected it is possible to give a better upper bound
than 1 for
ʻ
2
. We will explain this bound and also use it to design a randomized
logspace algorithm for UREACH.
Suppose
ʻ
and
ʻ
are distinct eigenvalues of
A
, and
x
and
x
be correspond-
ing eigenvectors. Then we claim
x
and
x
are mutually orthogonal. That is to say,
x
T
x
=
1
0. The claim holds because
x
T
Ax
=
ʻ
x
T
x
as well as
x
T
Ax
=
ʻ
x
T
x
and
ʻ
=
ʻ
.
