Information Technology Reference
In-Depth Information
2.2.2 1-L Reductions
1-L reductions are functions computed by logspace-bounded Turing machines that
make a single pass over their input tape (from left to right). They were introduced
by Hartmanis, Immerman, and Mahaney [
HIM78
,
HM81
] for many of the same
reasons that had led Jones to introduce log-bounded rudimentary reductions. 1-L
reductions offered the advantages of being significantlymore convenient and intuitive
(since the original formulation of log-bounded rudimentary reductions lacked the
intuitive appeal of the AC
0
formulation). In this brief overview, we avoid giving
more detailed definitions of 1-L reductions, but it is appropriate to note that there are
some differences in the formulations as presented in [
HIM78
] and [
HM81
], and that
some of these formulations result in a class of reductions that is not closed under
composition (see [
All88
]).
1-L reductions are easy to invert, and this fact, combined with some diagonaliza-
tion techniques, enabled a proof that all sets complete for PSPACE under 1-L reduc-
tions are p-isomorphic [
All88
]. They are not isomorphic under 1-L isomorphisms
[
BH92
], but they are complete under isomorphisms computable in nondeterministic
logspace [
HH93
].
Agrawal and Biswas [
AB96
] succeeded in showing that, even for classes as small
as deterministic logspace (and indeed, for any class that is closed under logspace
reductions that produce output at most linearly longer than the input) the sets complete
under 1-L reductions are complete under one-one, length-increasing, polynomial-
time invertible reductions. (Thus by [
BH77
] all such sets are p-isomorphic.) Finally,
Agrawal proved that all such sets are isomorphic via reductions computed by one-
way nondeterministic logspace (1-NL) machines [
Agr96
] (and the same paper proves
an analog of the Berman-Hartmanis conjecture for 1-NL reductions).
At this point, study of the structure of sets complete under 1-L reductions effec-
tively stopped.
1
The major open questions had been solved. But this was merely
a prelude to a much more exciting and significant development in the history of
work on the isomorphism problem, focusing on reductions that are computable by
constant-depth circuits. Indeed, although there are problems (such as the PARITY
problem) that are computable by 1-L machines but are not computed by AC
0
circuits
[
FSS84
], Agrawal had shown that, for essentially all complexity classes of interest,
all sets complete under 1-L reductions
are
complete under reductions computable in
AC
0
[
Agr96
]. And whereas all functions computable by 1-L machines are easy to
invert, this is not the case for AC
0
. Thus, by considering AC
0
reductions, the research
community was moving on to a richer class of complete sets, and was confronting
some of the essential issues raised by the Encrypted Complete Set Conjecture.
1
This is not to suggest that work on 1-L computation stopped. Indeed, much of the very large body
of work on
streaming algorithms
consists of the study of 1-L computation.
