Information Technology Reference
In-Depth Information
(
)
have
O
size descriptions. More precisely, a configuration is described by the
current state, the head position on the input tape (which requires log
n
bits), the head
position on the work tape (which requires log log
n
bits), along with the contents of
theworktapewhichis
O
log
n
bits. Furthermore, given two configurations
I
and
I
we can easily check from the description of the machine
M
if
M
can go from
I
to
I
in one step. Thus, in polynomial in
n
time we can define a directed graph
whose nodes are the configurations and edges are
(
log
n
)
if
M
can move from
I
to
I
in one step. Clearly,
M
accepts
x
if and only if there is a directed path from the initial
configuration to an accepting configuration. This can be solved in polynomial time
by a DFS-based algorithm. Thus, there is a polynomial time algorithm to determine
if
M
accepts
x
.
I
)
(
I
,
It is an open problem whether L equals NL. The L versus NL problem makes an
interesting study in contrast with the P versus NP problem as the results explained
in this section will show.
In order to talk about NL-complete problems, we can define logspace many-
one reductions:
f
:
ˇ
∗
ₒ
ˇ
∗
is logspace computable if there is a deterministic
logspace-bounded Turing machine that on input
x
,
i
computes the
i
th bit of
f
(
x
)
(if
i
themachine indicates that the
i
th bit is undefined). It is easy to check that the
composition of logspace computable functions is logspace computable. A language
A
>
|
f
(
x
)
|
ↆ
ˇ
∗
is NL-complete if
A
∈
NL and for every language
B
∈
NL,
B
is logspace
many-one reducible to
A
.
Let REACH
={
G
,
s
,
t
|
G
is a directed graph with a directed path from
s
to
t
}
.
Exercise
Show that
REACH
is NL-complete (Hint: use the configuration graph from
the proof of Proposition 5.1 for the reduction).
Unlike NP and coNP which are believed to be different, the classes NL and
coNL are equal. This result was shown independently by Immerman and Szelepcenyi
[
Imm88
,
Sze88
] in 1987. The Immerman-Szelepcenyi theorem was an important
breakthrough in our understanding of nondeterministic complexity classes.
Theorem 5.2
(Immerman-Szelepcenyi) [
Imm88
,
Sze88
]
For any space-construc-
tible function s
(
n
)
≥
log
n the classes
NSPACE
[
s
(
n
)
]
and co
NSPACE
[
s
(
n
)
]
are
equal. In particular,
NL
=
coNL
.
A formal detailed proof can be found in a textbook [
Pap94
, Theorem 7.6].
The foll
owing exercise outlines the proof with hints for the ambitious reader. Let
REACH
={
G
,
s
,
t
|
G
is a digraph with no
s
-to-t directed path
}
.
Exercise
1. Show that in
order to
prove NL
=
coNL it suffices to give an NL algorithm for
the problem REACH.
2. Let
be an input instance of REACH. Suppose the number
N
of vertices
in
G
that are reachable from
s
is given to the algorithm as additional input. Then
design an NL algorithm that accepts
(
G
,
s
,
t
)
(
G
,
s
,
t
)
precisely when there is no directed
s
-to-
t
path in
G
.
