L-Printable Sets.
A language is L-printable if there is a logspace algorithm which, on input 1n, prints all members in the language of length n.  Following the work of Allender and Rubinstein [SIAM J. Comput., 17 (1988), pp. 1193--1202] on P-printable sets, we present some simple properties of the L-printable sets. This definition of "L-printable" is robust and allows us to give alternate characterizations of  the L-printable sets in terms of tally sets and Kolmogorov complexity.  In addition, we show that a regular or context-free language is L-printable if and only if it is sparse, and  we investigate the relationship between L-printable sets, L-rankable sets (i.e., sets A having a logspace algorithm that, on input x, outputs the number of elements of A that precede x in the standard lexicographic ordering of strings), and the sparse sets in L.  We prove that under reasonable complexity-theoretic assumptions, these three classes of sets are all different.  We also show that the class of sets of small generalized Kolmogorov space complexity is exactly the class of sets that are L-isomorphic to tally languages.
Introduction
. What is an easy set? Typically, complexity theorists view
easy sets as those with easy membership tests. An even stronger requirement might
be that there is an easy algorithm to print all the elements of a given length. These
"printable" sets are easy enough that we can efficiently retrieve all of the information
we might need about them.
Hartmanis and Yesha first defined P-printable sets in 1984 [HY84]. A set A is
P-printable if there is a polynomial-time algorithm that on input 1 n outputs all of
the elements of A of length n. Any P-printable set must lie in P and be sparse, i.e.,
the number of strings of each length is bounded by a fixed polynomial of that length.
Allender and Rubinstein [AR88] give an in-depth analysis of the complexity of the
P-printable sets.
Once P-printability has been defined, it is natural to consider the analogous notion
of logspace-printability. Since it is not known whether or not an obvious question
to ask is: do the L-printable sets behave differently than the P-printable sets? In
this paper, we are able to answer this question in the affirmative, at least under plausible
complexity theoretic assumptions. Jenner and Kirsig [JK89] define L-printability
as the logspace computable version of P-printability. Because L-printability implies
P-printability, every L-printable set must be sparse and lie in L. In this paper we give
the first in-depth analysis of the complexity of L-printable sets. (Jenner and Kirsig
focused only one chapter on printability, and most of their printability results concern
NL-printable sets.)
y Department of Computer Science, University of Chicago, Chicago, IL 60637. The work of this
author was supported in part by NSF grant CCR-9253582.
z Department of Computer Science, University of Kentucky, Lexington, KY 40506-0046. The
work of these authors was supported in part by NSF grant CCR-9315354.
x DIMACS Center, Rutgers University, Piscataway, NJ 08855. The work of this author was
supported by NSF cooperative agreement CCR-9119999 and a grant from the New Jersey Commission
on Science and Technology.
- The work of this author was supported in part by a University of Kentucky Presidential
Fellowship.
L. FORTNOW, J. GOLDSMITH, M. LEVY, AND S. MAHANEY
Whenever a new class of sets is analyzed, it is natural to wonder about the
structure of those sets. Hence, we examine the regular and context-free L-printable
sets. Using characterizations of the sparse regular and context-free languages, we show
in x 4 that every sparse regular or context-free language is L-printable. (Although
the regular sets are a special case of the context-free sets, we include the results for
the regular languages because our characterization of the sparse regular languages is
simple and intuitive.)
We might expect many of the properties of P-printable sets to have logspace
analogues, and, in fact, this is the case. In x 5 we show that L-printable sets (like
their polynomial-time counterparts) are closely related to tally sets in L, and to sets
in L with low generalized space-bounded Kolmogorov complexity.
A set is said to have small generalized Kolmogorov complexity if all of its strings
are highly compressible and easily restorable. Generalized time-bounded Kolmogorov
complexity and generalized space-bounded Kolmogorov complexity are introduced in
[Har83] and [Sip83]. Several researchers [Rub86, BB86, HH88] show that P-printable
sets are exactly the sets in P with small generalized time-bounded Kolmogorov com-
plexity. [AR88] show that a set has small generalized time-bounded Kolmogorov
complexity if and only if it is P-isomorphic to a tally set. Using similar techniques,
we show in x 5 that the L-printable sets are exactly the sets in L with small generalized
space-bounded Kolmogorov complexity. We also prove that a set has small
generalized space-bounded Kolmogorov complexity if and only if it is L-isomorphic to
a tally set.
In x 6, we note that sets that can be ranked in logspace (i.e., given a string x,
a logspace algorithm can determine the number of elements in the set - x) seem
different from the L-printable sets. For sparse sets, P-rankability is equivalent to P-
printability. We show a somewhat surprising result in x 6, namely that the sparse
L-rankable sets and the L-printable sets are the same if and only if there are no tally
sets in P \Gamma L if and only if
Are all sparse sets in L either L-printable or L-rankable? Allender and Rubinstein
[AR88] show that every sparse set in P is P-printable if and only if there are no
sparse sets in FewP \Gamma P. In x 6, we similarly show a stronger collapse: every sparse
set in L is L-printable if and only if every sparse set in L is L-rankable if and only if
there are no sparse sets in FewP \Gamma L if and only if
Unlike L-printable sets, L-rankable sets may have exponential density. Blum
(see [GS91]) shows that every set in P is P-rankable if and only if every #P function
is computable in polynomial time. In x 6, we also show that every set in L is L-rankable
if and only if every #P function is computable in logarithmic space.
2. Definitions. We assume a basic familiarity with Turing machines and Turing
machine complexity. For more information on complexity theory, we suggest
either [BDG88] or [Pap94]. We also assume a familiarity with regular languages and
expressions and context-free languages as found in [Mar91]. We denote the characteristic
function of A by -A . We use the standard lexicographic ordering on strings and
let jwj be the length of the string w. (Recall that w - lex v iff jwj ! jvj or
and, if i is position of the leftmost bit where w and v differ, w .) The alphabet
all strings are elements of \Sigma   . We denote the complement of A by A.
The class P is deterministic polynomial time, and L is deterministic logarithmic
space; remember that in calculating space complexity, the machine is assumed to have
separate tapes for input, computation, and output. The space restriction applies only
to the work tape. It is known that L ' P, but it is not known whether the two classes
L-PRIN


are equal. The class E is deterministic time 2 O(n) , and LinearSPACE is deterministic
space O(n).
Definition 2.1. A set A is in the class PP if there is a polynomial time nondeterministic
Turing machine that, on input x, accepts with more than half its computations
A. A function f is in #P if there is a polynomial time nondeterministic
Turing machine M such that for all x, f(x) is the number of accepting computations
of M(x).
Allender[All86] defined the class FewP. FewE is defined analogously.
Definition 2.2. [All86] A set A is in the class FewP if there is a polynomial
time nondeterministic Turing machine M and a polynomial p such that on all inputs
accepts x on at most p(jxj) paths. A set A is in the class FewE if there is an
exponential time nondeterministic Turing machine M and a constant c such that on
all inputs x, M accepts x on at most 2 cn paths. (Note that this is small compared
to the double exponential number of paths of an exponential-time nondeterministic
Turing machine.)
Definition 2.3. A set S is sparse if there is some polynomial p(n) such that for
all n, the number of strings in S of length n is bounded by p(n) (i.e., jS =n j - p(n) ).
set T over alphabet \Sigma is a tally set if T ' foeg   , for any character oe 2 \Sigma.
The work here describes certain enumeration properties of sparse sets in L. There
are two notions of enumeration that are considered: rankability and printability.
Definition 2.4. If C is a complexity class, then a set A is C-printable if and
only if there is a function computable in C that, on any input of length n, outputs all
the strings of length n in A.
Note that P-printable sets are necessarily in P, and are sparse, since all of the
strings of length n must be printed in time polynomial in n. Since every logspace
computable function is also computable in polynomial time, L-printable sets are also
P-printable, and thus are also sparse.
Definition 2.5. If C is a complexity class, then a set, A, is C-rankable if and
only if there is a function r A computable in C such that r A
(In other words, r A (x) gives the lexicographic rank of x in A.) The function r A is
called the ranking function for A.
Note that P-rankable sets are necessarily in P but are not necessarily sparse.
Furthermore, a set is P-rankable if and only if its complement is P-rankable. Finally,
note that any P-printable set is P-rankable.
Definition 2.6. If C is a complexity class, then two sets, A and B, are C-
isomorphic there are total functions f and g computable in C that are
both one-one and onto, such that y, and f is a reduction
from A to B, and g is a reduction from B to A.
In order for two sets to be P-isomorphic, their density functions must be close to
each other: if one set is sparse and the other is not, then any one-one reduction from
the sparse set to the dense set must have super-polynomial growth rate. By the same
argument, if one has a super-polynomial gap, the other must have a similar gap.
A lexicographic (or order-preserving) isomorphism from A to B is, informally, a
bijection that maps the ith element of A to the ith element of B and maps the ith
element of A to the ith element of B. Note that in the definition of similar densities,
the isomorphisms need not be computable in any particular complexity class. This
merely provides the necessary condition on densities in order for the two sets to be
P-isomorphic or L-isomorphic.
Definition 2.7. Two sets, A and B, have similar densities if the lexicographic
4 L. FORTNOW, J. GOLDSMITH, M. LEVY, AND S. MAHANEY
isomorphisms from A to B and from B to A are polynomial size bounded.
The notion of printability, or of ranking on sparse sets, can be considered a
form of compression. Another approach to compression is found in the study of
Kolmogorov complexity; a string is said to have "low information content" if it it
has low Kolmogorov complexity. We are interested in the space-bounded Kolmogorov
complexity class defined by Hartmanis [Har83].
Definition 2.8. Let M v be a Turing machine, and let f and s be functions on
the natural numbers. Then we define
and M v uses s(n) space)g:
Following the notation of [AR88], we refer to y as the compressed string, f(n) as
the compression, and s(n) as the restoration space. Hartmanis [Har83] shows that
there exists a universal machine M u such that for all v, there exists a constant c such
that KS v [f(n); s(n)] ' KS u the subscript and let
3. Basic Results. We begin by formalizing some observations from the previous
section.
Observation 3.1. If A is L-printable, then A has polynomially bounded density,
i.e., A is sparse.
This follows immediately from the fact that logspace computable functions are P-time
computable (i.e., L-printability implies P-printability), and from the observations
on P-printable sets.
Proposition 3.2 ([JK89]). If A is L-printable, then A 2 L.
Proof. To decide x 2 A, simulate the L-printing function for A with input 1 jxj .
As each y 2 A is "printed," compare it, bit by bit, with x. If accept. Because
the comparisons can be done using O(1) space, and the L-printing function takes
O(log jxj) space, this is a logspace procedure.
Proposition 3.3. If A is L-rankable, then A 2 L.
Proof. Note that the function x \Gamma 1 (the lexicographic predecessor of x) can be
computed (though not written) in space logarithmic in jxj. Since logspace computable
functions are closed under composition, r A can be computed in logspace, as
can r A
Proposition 3.4. If A is L-printable, then A is L-rankable.
Proof. To compute the rank of x, we print the strings of A up to jxj and count the
ones that are lexicographically smaller than x. Since A is sparse, by Observation 3.1,
we can store this counter in logspace.
We can now prove the following, first shown by [JK89] with a different proof.
Proposition 3.5 ([JK89]). If A is L-printable, then A is L-printable in lexicographically
increasing order.
Proof. To prove this, we use a variation on selection sort. Suppose the logspace
machine M L-prints A. Then we can construct another machine, N , to L-print A in
lexicographically increasing order. Note that it is possible to store an instantaneous
description of a logspace machine, i.e., the position of the input head, the state, the
contents of the worktape, and the character just output, in O(log jxj) space.
The basic idea is that we store, during the computation, enough information
to produce three strings: the most recently printed string (in the lexicographically
ordered printing), the current candidate for the next string to be printed, and the
L-PRIN


current contender. We can certainly store three IDs for M in logspace. Each ID
describes the state of M immediately prior to printing the desired string.
In addition to storing the IDs, we must simulate M on these three computations
in parallel, so that we can compare the resulting strings bit by bit. If the contender
string is greater than the last string output (so it has not already been output) and
less than the candidate, it becomes the new candidate. Otherwise, the final ID of
the computation becomes the new contender. These simulated computations do not
produce output for N ; when the next string is found for N to print, its initial ID is
available, and the simulation is repeated, with output.
Using the same technique as in the previous proof, one can easily show the following

Proposition 3.6. If A is L-printable, and A - =log B, then B is L-printable as
well.
4. L-Printable Sets. We begin this section with a very simple example of a
class of L-printable sets.
Proposition 4.1 ([JK89]). The tally sets in L are L-printable.
Proof. On input of length n, decide whether 1 n 2 A. If so, print it.
One may ask, are all of the L-printable sets as trivial as Proposition 4.1? We
demonstrate in the following sections that every regular language or context-free language
that is sparse is also L-printable (see Theorem 4.5 and Corollary 4.14). We also
give an L-printable set that is neither regular nor context-free (see Proposition 4.15).
4.1. Sparse Regular Languages. We show that the sparse regular languages
are L-printable. In order to do so, we give some preliminary results about regular
expressions.
Definition 4.2 ([BEGO71]). Let r be a regular expression. We say r is unambiguous
if every string has at most one derivation from r.
Theorem 4.3 ([BEGO71]). For every regular language L, there exists an unambiguous
regular expression r such that
Proof. (Sketch) Represent L as the union of disjoint languages whose DFA's have
a unique final state. Using the standard union construction of an NFA from a DFA,
we get an NFA with the property that each string has a unique accepting path. Now,
using state elimination to construct a regular expression from this NFA, the unique
path for each string becomes a unique derivation from the regular expression.
We should note that even though removal of ambiguity from a regular expression
is, in general, PSPACE-complete [SH85], this does not concern us. Theorem 4.3
guarantees the existence of an unambiguous regular expression corresponding to every
regular language, that is sufficient for our needs.
We now define a restricted form of regular expression, that will generate precisely
the sparse regular languages. (Note that a similar, although more involved, characterization
was given in [SSYZ92]. They give characterizations for a variety of densities,
whereas we are only concerned with sparse sets.)
Definition 4.4. We define a static regular expression (SRE) on an alphabet \Sigma
inductively, as follows:
1. The empty expression is an SRE, and defines ;, the empty set.
2. If x 2 \Sigma or string ), then x is an SRE.
3. If s and t are SREs, then st, the concatenation of s and t, is an SRE.
4. If s and t are SREs, then s + t, the union of s and t, is an SRE.
5. If s is an SRE, then s   is an SRE iff:
a) s does not contain a union of two SREs; and,
6 L. FORTNOW, J. GOLDSMITH, M. LEVY, AND S. MAHANEY
b) s does not contain any use of the   operator.
Note the restriction of the   operator in the above definition. I.e.,   can only be
applied to a string. This is the only difference between SREs and standard regular
expressions.
We can alternately define an SRE as a regular expression that is the sum of terms,
each of that is a concatenation of letters and starred strings.
Theorem 4.5. Let R be an unambiguous regular expression. Then L(R) is sparse
iff R is static.
Proof. We first prove two lemmas about "forbidden" subexpressions.
Lemma 4.6. Let ff, fi; S be non-empty regular expressions such that
and S is unambiguous. Then there is a constant k ? 0 such that, for infinitely many
k strings of length n.
Proof. Let  such that u 2 L(ff) and v 2 L(fi). Let
S is unambiguous, there must be at least two strings of length k in L(S), namely u jvj
and v juj . So, for any length n such that there are at least 2
strings of length n in L(S).
Lemma 4.7. Let ff, fi; S be non-empty regular expressions such that S is unam-
biguous, where S is either of the form (ff   fi)   or of the form (fffi   )   . Then, there is
a constant k such that, for infinitely many n,
k strings of length n.
Proof. Let  such that u 2 L(ff) and v 2 L(fi). Suppose
jvj. If S is unambiguous, there are at least two distinct strings of length
k in L(S), namely, u jvj v and v juj+1 . So, for any length n such that
there are at least 2
k strings of length n in L(S).
The proof is very similar if unambiguous.
It is clear that unambiguity is necessary for both lemmas. For example, the
is not static, but L((a that is sparse.
Note that if R is the empty expression, the theorem is true, since R is static, and
which is certainly sparse. So, for the rest of the proof, we will assume that
R is non-empty.
To show one direction of Theorem 4.5, suppose R is not static. Then it contains
a subexpression that is either of the form (fl or of the form (fl 0 ff   In
the first case, by a small modification to the proof of lemma 4.6, L(R) is not sparse.
In the second case, by a similar modification to the proof of lemma 4.7, L(R) cannot
be sparse.
Now, suppose R is static. If contains only the string x. If
is either a string of characters or a single character, L(R) can have
at most one string of any length.
are SREs. Let p r (n) and p s (n) bound the
number of strings in L(r) and L(s), respectively. Then there are at most p r (n)+p s (n)
strings of length n.
Finally, suppose are SREs. Let p r (n) and p s (n) bound
the number of strings in L(r) and L(s), respectively. Then, the number of strings of
length n is:
The degree of q is bounded by 1
on the complexity of R, L(R) is sparse.
L-PRIN


Note that the second half of the proof does not use unambiguity. Hence, any
static regular expression generates a sparse regular language.
Theorem 4.8. Let R be an SRE. Then L(R) is L-printable.
Proof. Basically, we divide R into terms that are either starred expressions or
non-starred expressions. For example, we would divide 0(1
into three parts: 0(1 internally L-print each
term independently, and check to see if the strings generated have the correct length.
In our example, to print strings of length 9, we might generate 0110, 11, and 0011,
respectively, and check that the combined string is in fact 9 characters long. (In this
case, the string is too long, and is not printed.)
Let k be the number of stars that appear in R. Partition R into at most 2k
subexpressions, k with stars, and the others containing no stars.
The machine to L-print L(R) has two types of counters. For each starred subex-
pression, the machine counts how many times that subexpression has been used. For
a string of length n, no starred subexpression can be used more than n times. Each
counter for a starred subexpression only needs to count up to n.
Each non-starred subexpression generates only a constant number of strings.
Thus, up to k +1 additional counters, each with a constant bound, are needed. (Note
that the production may intermix the two types of counters, for instance if (x
occurs.)
The machine uses two passes for each potential string. First, the machine generates
a current string, counting its length. If the string is the correct length, it
regenerates the string and prints it out. Otherwise, it increments the set of counters,
and continues. In this way, all strings of lengths - n are generated, and all strings of
length n are printed.
Lastly, we need to argue that this procedure can be done by a logspace machine.
Each of the at most 2k must count up to n (for n sufficiently large, say,
larger than jRj). Thus, the counting can be done in log n space. In addition, the
actual production of a string requires an additional counter, to store a loop variable.
The rest of the computation can be handled in O(1) space, using the states of the
machine. Thus, L(R) is L-printable.
Note that this L-printing algorithm may generate some strings in L(R) more than
once. To get a non-redundant L-printer, simply modify the program to output the
strings in lexicographic order, as in Proposition 3.5, or use an unambiguous SRE for
L(R).
Theorem 4.8 does not characterize the L-printable sets, as we see below.
Proposition 4.9. There exists a set S such that S is L-printable and not regular

Proof. The language L-printable (for any n, we print out
only if n is even), but not regular.
4.2. Sparse Context-Free Languages. Using the theory of bounded context-free
languages we can also show that every sparse context-free language is L-printable.
Definition 4.10. A set A is bounded if there exist strings w such that
Note the similarity between bounded languages and languages generated by SRE's.
Note also that every bounded language is sparse.
Ibarra and Ravikumar [IR86] prove the following.
8 L. FORTNOW, J. GOLDSMITH, M. LEVY, AND S. MAHANEY
Theorem 4.11 ([IR86]). If A is a context-free language then A is sparse if and
only if A is bounded.
Ginsburg [Gin66, p. 158] gives the following characterization of bounded context-free
languages.
Theorem 4.12 ([Gin66]). The class of bounded context-free languages is the
smallest class consisting of the finite sets and fulfilling the following properties.
1. If A and B are bounded context-free languages then A [ B is also a bounded
context-free language.
2. If A and B are bounded context-free languages then
is also a bounded context-free language.
3. If A is a bounded context-free language and x and y are fixed strings then the
following set is also a bounded context-free language.
ay
Corollary 4.13. Every bounded context-free language is L-printable.
Proof. Every finite set is L-printable. The L-printable sets are closed under the
three properties in Theorem 4.12.
Corollary 4.14. Every sparse context-free language is L-printable.
This completely characterizes the L-printable context-free languages. However
the sparse context-free languages do not characterize the L-printable languages.
Proposition 4.15. There exists an L-printable set S such that S is not context-free

Proof. The language is L-printable, but is not context-free.
5. L-Isomorphisms. It is easy to show that two P-printable sets, or P-rankable
sets, of similar densities are P-isomorphic. Since the usual proof relies on binary
search, it does not immediately extend to L-rankable sets. However, we are able to
exploit the sparseness of L-printable sets to show the following.
Theorem 5.1. If A and B are L-printable and have similar densities, then A
and B are L-isomorphic (i.e., A - =log B).
Proof. For each x, define y x to be the image of x in the lexicographic isomorphism
from A to B. Since A and B are L-printable, they are both sparse. Let p(n) be a
strictly increasing polynomial that bounds the densities of both sets. If
x is "close" to y x , in the sense that there are at most p(jxj) strings between them in
the lexicographic ordering. (Recall Definition 2.7.) In fact, for all x, jy x
Let r A (x) be the rank of x in A. If
A, then the rank of x in A is
Furthermore, is the unique element of B for which
this holds. Note that both r A (x) and r B (y x ) can be written in space O(log jxj). Thus,
to compute y x , we need to compute do so by maintaining
a variable d, that is initialized to r A (x). Counter c is initialized to 0. The following
loop is iterated until a counter, c, reaches p(jxj
1. L-print (in lexicographic order) the elements of B of length c; for each string
that is lexicographically smaller than decrement d;
2. increment c.
Note that, if d is written on the work tape, each bit of x \Gamma d can be computed
in logspace as needed, and the output of the L-printing function can be compared to
in a bit-by-bit manner.
L-PRIN


If x 2 A, since the L-printing function outputs strings in lexicographic order,
computing y x is easy: compute r A (x), then "L-print" B internally, actually outputting
the r A (x) th string.
Without loss of generality, we can assume that the simulated L-printer for B
prints B in lexicographic order. Thus, as soon as the r A 1st element of B is
printed internally, the simulation switches to output mode.
The following is an overview of the logspace algorithm computing the desired
isomorphism.
1. Compute A(x).
2. Compute r A (x), and write it on a work tape.
3. If x 2 A, find the r A (x) th element of B, and output it.
4. If
find the unique string y
and output y x .
Using this theorem, we can now characterize the L-printable sets in terms of
isomorphisms to tally sets, and in terms of sets of low Kolmogorov space complexity.
Theorem 5.2. The following are equivalent:
1. S is L-printable.
2. S is L-isomorphic to some tally set in L.
3. There exists a constant k such that S ' KS[k log n; k log n] and S 2 L.
Although it is not known whether or not every sparse L-rankable set is L-isomor-
phic to a tally set (see Theorem 6.1), we can prove the following lemma, that will be
of use in the proof of Theorem 5.2.
Lemma 5.3. Let A be sparse and L-rankable. Then there exists a tally set T 2 L
such that A and T have similar density.
Proof. Let A -n denote the strings of length at most n in A. Let p(n) be an
everywhere positive monotonic increasing polynomial such that jA -n j - p(n) for all
n, and such that greater than the number of strings of length n in
A. Let r(x) be the ranking function of A. We define the following tally set:
To show that T 2 L, notice that of the tally strings 1 i ,
the largest n such that p(n \Gamma that n can be written in binary
in space O(log m).) Then compute d This difference is bounded by
p(n), and thus can be written in logspace. Finally, compute d
compare to d 1 . Accept iff d 1 - d 2 .
Finally, we show that T and A have similar density. Let f : A ! T be the
lexicographic isomorphism between T and A. Note that f maps strings of length n to
strings of length at most p(n), so f is polynomially bounded. Note that p is always
positive, which implies that f is length-increasing. must also be polynomially
bounded. Thus, T and A have similar density.
The following proof of Theorem 5.2 is very similar to the proof of the analogous
theorem in [AR88].
Proof. [1 be L-printable. Then it is sparse and L-rankable. Let T be
the tally set guaranteed by Lemma 5.3. By Proposition 4.1, T is L-printable. Thus,
T and S are L-printable, and T and S have similar density. So by Theorem 5.1,
L. FORTNOW, J. GOLDSMITH, M. LEVY, AND S. MAHANEY
[2 be L-isomorphic to a tally set T , and let f be the L-isomorphism
from S to T . Let x 2 S be a string of length n. Let logspace
computable, there exists a constant c such that r - n c , i.e., jrj - c log n. In order to
recover x from r, we only have to compute f Computing 0 r given r requires
log n space for one counter. Further, there exists a constant l such that computing
requires at most lc log n space, since r - n c . So, the total space needed to
compute x given r is less than or equal to log n+ lc log n - k log n for some k. Hence,
log n]. If T 2 L, then S 2 L, since S - =log T .
[3 log n] for some k, and S 2 L. On input 0 n , we
simulate M u for each string of length k log n. For a given string x, log n, we
first simulate M u (x) and check whether it completes in space k log n. If it does, we
recompute M u (x), this time checking whether the output is in S. If it is, we recompute
M u (x), and print out the result. The entire computation only needs O(log n) space,
so S is L-printable.
It was shown in [AR88] that a set has small generalized Kolmogorov complexity
if and only it is P-isomorphic to a tally set. (Note: this was improvement of the result
in [BB86], which showed that a set has small generalized Kolmogorov complexity if
and only if it is "semi-isomorphic" to a tally set.) Using a similar argument and Theorem
5.2 we can show an analogous result for sets with small generalized Kolmogorov
space complexity. First, we prove the following result.
Proposition 5.4. For all M v and k, KS v [k log n; k log n] is L-printable.
Proof. To L-print for length n, simulate M v on each string of length less than or
equal to k log n, and output the results.
Corollary 5.5. There exists a k such that A ' KS[k log n; k log n] if and only
if A is L-isomorphic to a tally set.
Proof. Suppose A is L-isomorphic to a tally set. Then, by the argument given in
the proof of [2 ) 3] in Theorem 5.2, A ' KS[k log n; k log n].
suppose A ' KS[k log n; k log n]. By Proposition 5.4 and Theorem 5.2,
KS[k log n; k log n] is L-isomorphic to a tally set in L via some L-isomorphism f . It
is clear that A is L-isomorphic to f(A). Since f(A) is a subset of a tally set, f(A)
must also be a tally set.
6. Printability, Rankability and Decision. In this section we examine the
relationship among L-printable sets, L-rankable sets and L-decidable sets. We show
that any collapse of these classes, even for sparse sets, is equivalent to some unlikely
complexity class collapse.
Theorem 6.1. The following are equivalent:
1. Every sparse L-rankable set is L-printable.
2. There are no tally sets in
Proof. [2 , 3] This equivalence follows from techniques similar to those of
Suppose A is a sparse L-rankable set. Note that A 2 L.
Let
ith bit of the jth string in A is 1g;
where
L-PRIN


Note that hi; ji can be computed in space linear in jij + jjj. Since A is sparse, i and
are bounded by a polynomial in the length of the jth string. Hence, hi; ji can be
computed using logarithmic space with respect to the length of the jth string.
Given hi; ji, we can determine i and j in polynomial time, and we can find the
jth string of A by using binary search and the ranking function of A. Hence, T 2 P.
So, by assumption, T 2 L.
Next we give a method for printing A in logspace. Given a length n, we compute
(and store) the ranks of 0 n and 1 n in A. Let r start and r end be the ranks of 0 n and
the string with rank r start has length less than n. First,
we check to see if 0 n 2 A, and if so, print it. Then, for each j, r start
we output the jth string by computing and printing T (1 hi;ji ) for each bit i. This
procedure prints the strings of A of length n.
Note that since A is sparse, we can store r start and r end in O(log n) space. Since
store and increment the current value of i in log n space.
[1 be a tally set. Since the monotone circuit value problem
is P-complete (see [GHR95]), there exists a logspace-computable function f and a
nondecreasing polynomial p such that f(n) produces a circuit Cn with the following
properties.
1. Cn is monotone (i.e., Cn uses only AND and OR gates).
2. Cn has p(n) gates.
3. The only inputs to Cn are 0 and 1.
4. Cn outputs 1 iff 1 n is in T .
We can assume that the reduction orders the gates of Cn so that the value of
gate depends only on the constants 0 and 1 and the values of gates g j for
([GHR95]). Let xn be the string of length p(n) such that the ith bit of xn is the value
of gate g i .
Ng. Then A contains exactly one string of length p(n) for all
n, and no strings of any other lengths.
6.1.1. The set A is L-rankable.
Proof. To prove this claim, let w be any string. In logspace, we can find the
greatest n such that p(n) - jwj. If p(n) 6= jwj then w 62 A, and the rank of w is n.
Suppose xn is the only string of length p(n) in A, the rank of w is
Consider the ith bit of w as a potential value for gate g i in Cn . Let j be the
smallest value such that w j is not the value of g j . In order to find the value of a gate
i , we first use f(n) (our original reduction) to determine the inputs to g i . By the
time we consider the i th bit of w, we know that w is a correct encoding of all of the
gates g k such that k ! i, so we can use those bits of w as the values for the gates.
Thus, we can determine the value of g i and compare it to the ith bit of w. If they
differ, we are done. If they are the same, we continue with the next gate. We can
count up to p(n) in logspace, so this whole process needs only O(log p(n)) space to
compute.
Once j is found, there are three cases to consider.
1. If j doesn't exist then
2. If the jth bit of w is 0 then w ! xn .
3. If the jth bit of w is 1 then w ? xn .
These follow since the ith bit of xn matches the ith bit of w for all
Thus A is L-rankable and, by assumption, L-printable.
12 L. FORTNOW, J. GOLDSMITH, M. LEVY, AND S. MAHANEY
So, to determine if 1 n is in T , L-print A for length p(n) to get xn . The bit of xn
that encodes the output gate of Cn is 1 iff 1 every step of this algorithm
is computable in logspace, T 2 L.
This completes the proof of Theorem 6.1.
Corollary 6.2. There exist two non-L-isomorphic L-rankable sets of the same
density, unless there are no tally sets in
Proof. Consider the sets T and A from the second part of the proof of Theorem 6.1.
The set has the same density as A. By Proposition 4.1, B is
L-printable. If A and B were L-isomorphic then by Proposition 3.6, A would also be
L-printable and T would be in L.
One may wonder whether every sparse set in L is L-printable or at least L-
rankable. We show that either case would lead to the unlikely collapse of FewP and
L. Recall that FewP consists of the languages in NP accepted by nondeterministic
polynomial-time Turing machines with at most a polynomial number of accepting
paths.
Fix a nondeterministic Turing machine M and an input x. Let p specify an
accepting path of M(x) represented as a list of configurations of each computation
step along that path. Note that in logarithmic space we can verify whether p is such
an accepting computation since if one configuration follows another only a constant
number of bits of the configuration change.
We can assume without loss of generality that all paths have the same length and
that no accepting path consists of all zero or all ones.
Define the set PM by
is an accepting path of M on xg:
From the above discussion we have the following proposition that we will use in the
proofs of Theorems 6.6 and 6.7.
Proposition 6.3. For any nondeterministic machine M , PM is in L.
Allender and Rubinstein [AR88] showed the following about P-printable sets.
Theorem 6.4 ([AR88]). Every sparse set in P is P-printable if and only if there
are no sparse sets in FewP \Gamma P.
Allender [All86] also relates this question to inverting functions.
Definition 6.5. A function f is strongly L-invertible on a set S if there exists
a logspace computable function g such that for every x 2 S, g(x) prints out all of the
strings y such that
We extend the techniques of Allender [All86] and Allender and Rubinstein [AR88]
to show the following.
Theorem 6.6. The following are equivalent.
1. There are no sparse sets in FewP \Gamma L.
2. Every sparse set in L is L-printable.
3. Every sparse set in L is L-rankable.
4. Every L-computable, polynomial-to-one, length-preserving function is strongly
L-invertible on f1g   .
5.
Proof. [1 A be a sparse set in L. Then A is in P. By (1) we have that
there are no sparse sets in FewP \Gamma P. By Theorem 6.4, A is P-printable.
Consider the following set B.
ith bit of the jth element of A of length n is bg
L-PRIN


Since A is P-printable then B is in P. By (1) (as B is sparse and in P ' FewP), we
have B is in L. Then A is L-printable by reading the bits off from B.
[2 ) 3] Follows immediately from Proposition 3.4.
[3 A be a sparse set in FewP accepted by a nondeterministic machine
M with computation paths of length q(n) for inputs of length n.
Consider the set PM defined as above. Note that PM is sparse since for any length
accepts a polynomial number of strings with at most a polynomial number
of accepting paths each. Also by Proposition 6.3 we have PM in L.
By (3) we have that PM is L-rankable. We can then determine in logarithmic
space whether M(x) accepts (and thus x is in A) by checking whether
r PM (x#0
[2 f be a L-computable, polynomial-to-one, length-preserving function.
Consider g. Since S is in L, S is L-printable.
A be a sparse set in L. Define x is in A and x otherwise.
If g is a strong L-inverse of f on 1   then g(1 n ) will print out the strings of length n of
A and 1 n . We can then print out the strings of length n in logspace by printing the
strings output by g(1 n ), except we print 1 n only if 1 n is in A.
[1 , 5] In [RRW94], Rao et al. show that there are no sparse sets in FewP \Gamma P if
and only if straightforward modification of their proofs is sufficient to
show that there are no sparse sets in FewP \Gamma L if and only if
Unlike L-printability, L-rankability does not imply sparseness. One may ask
whether every set computable in logarithmic space may be rankable. We show this
equivalent to the extremely unlikely collapse of PP and L.
Theorem 6.7. The following are equivalent.
1. Every #P function is computable in logarithmic space.
2.
3. Every set in L is L-rankable.
Our proof uses ideas from Blum (see [GS91]), who shows that every set in P is
P-rankable if and only if every #P function is computable in polynomial time. Note
that Hemachandra and Rudich [HR90] proved results similar to Blum's.
Proof. [1 A is in PP then there is a #P function f such that x is in A iff
the high-order bit of f(x) is one.
[2 implies that
. Thus we have and we can compute every bit of a #P function in
logarithmic space.
[1 A be in L. Consider the nondeterministic polynomial-time machine
M that on input x guesses a y - lex x and accepts if y is in A. The number of
accepting paths of M(x) is a #P function equal to r A (x).
[3 f be a #P function. Let M be a nondeterministic polynomial-time
machine such that f(x) is the number of accepting computations of M(x). Let q(n) be
the polynomial-sized bound on the length of the computation paths of M . Consider
PM as defined above. By Proposition 6.3 we have that PM is in L so by (3) PM is
L-rankable. We then can compute f(x) in logarithmic space by noticing
14 L. FORTNOW, J. GOLDSMITH, M. LEVY, AND S. MAHANEY
7. Conclusions. The class of L-printable sets has many properties analogous to
its polynomial-time counterpart. For example, even without the ability to do binary
searching, one can show two L-printable sets of the same density are isomorphic.
However, some properties do not appear to carry over: it is very unlikely that every
sparse L-rankable set is L-printable.
Despite the strict computational limits on L-printable, this class still has some
bite: every tally set in L, every sparse regular and context-free language and every
L-computable set of low space-bounded Kolmogorov complexity strings is L-printable.

Acknowledgments

. The authors want to thank David Mix Barrington for a
counter-example to a conjecture about sparse regular sets, Alan Selman for suggesting
the tally set characterization of L-printable sets and Corollary 5.5, Chris Lusena for
proofreading, and Amy Levy, John Rogers and Duke Whang for helpful discussions.
The simple proof sketch of Theorem 4.3 was provided by an anonymous referee. The
last equivalence of Theorem 6.6 was suggested by another anonymous referee. The
authors would like to thank both referees for many helpful suggestions and comments.



--R

The complexity of sparse sets in P

Sets with small generalized Kolmogorov complexity
Structural Complexity I
Ambiguity in graphs and expressions
Tally languages and complexity classes
The Mathematical Theory of Context-Free Languages
Limits to Parallel Computation: P-Completeness Theory
Compression and ranking
Generalized Kolmogorov complexity and the structure of feasible com- putations
On sparse oracles separating feasible complexity classes

Computation times of NP sets of different densities
ambiguity and other decision problems for acceptors and transducers
Alternierung und Logarithmischer Platz
Introduction to Languages and the Theory of Computation
Computational Complexity
Upward separation for FewP and related classes
A note on sets with small generalized Kolmogorov complexity

A complexity theoretic approach to randomness
Characterizing regular languages with polynomial densities
--TR

--CTR
Allender, NL-printable sets and nondeterministic Kolmogorov complexity, Theoretical Computer Science, v.355 n.2, p.127-138, 11 April 2006
context-free languages;sparse sets;kolmogorov complexity;ranking;l-isomorphisms;computational complexity;regular languages;logspace