Cryptography Reference
In-Depth Information
Testing whether or not a graph is connected is easily reduced to testing connectivity
between any given pair of vertices.
4
Thus, we focus on the task of determining whether
or not two given vertices are connected in a given graph.
Algorithm.
On input a graph
G
=
(
V
,
E
) and two vertices,
s
and
t
,wetakea
random
walk
of length
O
(
|
V
|·|
E
|
), starting at vertex
s
, and test at each step whether or not
vertex
t
is encountered. If vertex
t
is ever encountered, then the algorithm will accept;
otherwise, it will reject. By a random walk we mean that at each step we uniformly select
one of the edges incident at the current vertex and traverse this edge to the other endpoint.
Analysis.
Clearly, if
s
is not connected to
t
in the graph
G
, then the probability that the
foregoing algorithm will accept will be zero. The harder part of the analysis is to prove
that if
s
is connected to
t
in the graph
G
, then the algorithm will accept with probability
at least
2
3
. (The proof is deferred to Exercise 3.) Thus, either way, the algorithm will err
with probability at most
3
. The error probability can be further reduced by invoking
the algorithm several times (using fresh random choices in each try).
1.3.2.2. Randomized Algorithms: Two Points of View
Randomized algorithms (machines) can be viewed in two equivalent ways. One way of
viewing randomized algorithms is to allow the algorithm to make random moves (i.e.,
“toss coins”). Formally, this can be modeled by a Turing machine in which the transition
function maps pairs of the form (
) to two possible triples of the form
(
state
,
symbol
,
direction
). The next step for such a machine is determined by a
random choice of one of these triples. Namely, to make a step, the machine chooses at
random (with probability
state
,
symbol
1
2
for each possibility) either the first triple or the second one
and then acts accordingly. These random choices are called the
internal coin tosses
of
the machine. The output of a probabilistic machine
M
on input
x
is not a string but
rather a random variable that assumes strings as possible values. This random variable,
denoted
M
(
x
), is induced by the internal coin tosses of
M
.By
Pr
[
M
(
x
)
=
y
] we mean
the probability that machine
M
on input
x
will output
y
. The probability space is that
of all possible outcomes for the internal coin tosses taken with uniform probability
distribution.
5
Because we consider only polynomial-time machines, we can assume,
without loss of generality, that the number of coin tosses made by
M
on input
x
is
independent of their outcome and is denoted by
t
M
(
x
). We denote by
M
r
(
x
) the output
of
M
on input
x
when
r
is the outcome of its internal coin tosses. Then
Pr
[
M
(
x
)
=
y
]
4
The space complexity of such a reduction is low; we merely need to store the names of two vertices (currently
being tested). Alas, the time complexity is indeed relatively high; we need to invoke the two-vertex tester
2
times, where
n
is the number of vertices in the graph.
5
This sentence is slightly more problematic than it seems. The simple case is when, on input
x
, machine
M
always makes the same number of internal coin tosses (independent of their outcome). In general, the number of
coin tosses may depend on the outcome of prior coin tosses. Still, for every
r
, the probability that the outcome of
the sequence of internal coin tosses will be
r
equals 2
−|
r
|
if the machine does not terminate when the sequence
of outcomes is a strict prefix of
r
, and equals zero otherwise. Fortunately, because we consider polynomial-time
machines, we can modify all machines so that they will satisfy the structure of the simple case (and thus avoid the
foregoing complication).
