A language is L-printable if there is a logspace algorithm which, on input 1 n , 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.

A quasi-polynomial-time algorithm is presented for sampling almost uniformly at random from then-slice of the languageL(G) generated by an arbitrary context-free grammarG. (Then-slice of a languageLover an alphabetΣis the subsetL∩Σnof words of length exactlyn.) The time complexity of the algorithm isε−2(n |G|)O(log n)where the parameterεbounds the variation of the output distribution from uniform, and |G| is a natural measure of the size of grammarG. The algorithm applies to a class of language sampling problems that includes slices of context-free languages as a proper subclass. For the restricted case of homogeneous languages expressed by regular expressions without Kleene-star, a truly polynomial-time algorithm is presented.

Properties of L-printable sets are considered, and it is shown that two sets A and B that are L-printable and have similar density are L-isomorphic. L-printable sets are characterized as those sets L-isomorphic to tally sets in L, and as subsets of KS[k log n, k log n]. Several classes of L-printable sets are given, including sparse regular and context-free sets; a characterization of sparse regular sets is given. The relationship of the sparse sets in L to the sparse L-rank able and L-printable sets is considered, and strong indications are given that these classes are all different. An oracle is constructed relative to which there are sparse L-rankable sets that are in L and not L-printable, and L-rankable sets of similar density that are not L-isomorphic.

Berman and Hartmanis [1977] conjectured that there is a polynomial-time computable isomorphism between any two languages complete for NP with respect to polynomial-time computable many-one (Karp) reductions.Joseph and Young [1985] gave a structural definition of a class of NP-complete sets-the k-creative sets-and defined a class of sets (the K; 's) that are necessarily ~-creative.They went on to conjecture that certain of these K}'s are not isomorphic to the standard NP-complete sets.Clearly, the Berman-Hartmanis and Joseph-Young conjectures cannot both be correct.We introduce a family of strong one-way functions, the scrambling functions.If f is a scrambling function, then K} is not isomorphic to the standard NP-complete sets, as Joseph and Young conjectured, and the Berman-Hartmanis conjecture fails.Indeed, if scrambling functions exist, then the isomorphism also fails at higher complexity classes such as EXP and NEXP.As evidence for the existence of scrambling functions, we show that much more powerful one-way functions-the annihikzting functions-exist relative to a random oracle.Random oracles are the first examples of oracles relative to which the isomorphism conjecture fails with respect to higher classes such as EXP and NEXP.

Berman and Hartmanis [BH77] conjectured that there is a polynomial-time computable isomorphism between any two languages m-complete (“Karp” complete) for NP. Joseph and Young [JY85] discovered a structurally defined class of NP-complete sets and conjectured that certain of these sets (the Kkƒ's) are not isomorphic to the standard NP-complete sets for some one-way functions ƒ. These two conjectures cannot both be correct.

An m-degree is a collection of sets equivalent under polynomial-time many-one (Karp) reductions; for example, the complete sets for NP or PSPACE are m-degrees. An m-degree is collapsing iff its members are p-isomorphic, i.e., equivalent under polynomial time, 1-1, onto, polynomial time invertible reductions. L. Berman and J. Hartmanis showed that all the then known natural NP-complete sets are isomorphic, and conjectured that the m-degree of the NP-complete sets collapses, in essence claiming that there is only one NP-complete set. However, until now no nontrivial collapsing m-degree was known to exist. In this paper we provide the first examples of such degrees, In particular, we show that there is a collapsing degree which is btt-complete for EXP (the exponential time decidable sets) and that, for every set A, there is a collapsing degree which is hard for A. We also obtain analogous results for noncollapsing degrees.

An Inexact Agreement protocol alows processors that each have a value approximating $\hat{\nu}$ to compute new values that are closer to each other and close to $\hat{\nu}$. Two fault-tolerant protocols for Inexact Agreement are described. As long as fewer than 1/3 of the processors are faulty, the protocols give the required convergence; they also permit iteration and thus convergence to any desired precision. When between 1/3 and 2/3 of the processors are faulty, the protocols may not converge. However, then processors either detect that too many faults have occurred or the new values computed by processors remain close to each other and to $\hat{\nu}$. In this case, the divergence is bounded. Use of the protocols for clock synchronization in a distributed system is explained.

All known NP-complete sets are P-isomorphic (i.e. there are polynomial time, one-to-one and onto, polynomial time invertible reductions between any two known NP-complete sets) [BH]. If all NP-complete sets are P-isomorphic, then. P ≠ NP. However it is not known if the existence of more than one P-isomorphism class of NP-complete sets has implications for the P = NP? problem. In the main result of this paper we prove: Theorem: If there is an NP-complete set that is not P-isomorphic to SAT, then there are infinitely many NP-complete sets that are mutually non-P-isomorphic. Thus, the number of P-isomorphism classes of NP-complete sets is either one or (countably) infinite. Two proof techniques are developed in this paper: we use delayed diagonalization [BCH, L] to construct new sets that are not P-isomorphic to existing sets; the diagonalization conditions are used to defeat P-isomorphisms. We also examine certain properties of 'generic' NP-complete sets and introduce techniques based on padding functions to assure that the sets constructed will be NP-complete. The results on P-isomorphisms and constructing non-P-isomorphic sets apply also to sets complete for PTAPE, EXPTIME, and EXPTAPE and other classes. We also examine the structure of NP-complete sets based on size increasing, invertible reductions, The degrees are P-isomorphism classes [BH]. We show that if there is more than one degree, then there is an ω chain of degrees with SAT representing a maximal element.

In this paper we study languages accepted by nondeterministic $\log n$-tape automata that scan their input only once and relate their computational power to two-way $\log n$-tape automata. We show that for the one-way $\log n$-tape automata the nondeterministic model (1-NL) is computationally much more powerful than the deterministic model (1-L), that under one-way $\log n$-tape reductions there exist natural complete languages for these automata and that the complete languages cannot be sparse. Furthermore, we show that any language complete for nondeterministic one-way $\log n$-tape automata (under 1-L reductions) is also complete for the computationally more powerful nondeterministic two-way $\log n$-tape automata (NL) under two-way $\log n$-tape reductions. Therefore, for all bounds $T(n)$, $T(n) \geqq \log n$, the deterministic and nondeterministic $T(n)$-tape bounded computations collapse iff the nondeterministic one-way $\log n$-tape computations can be carried out by two-way deterministic log n-tape automata.

A set S ⊂ {0,1}* is sparse if there is a polynomial p such that the number of strings in S of size at most n is at most p(n). All known NP-complete sets, such as SAT, are not sparse. The main result of this paper is that if there is a sparse NP-complete set under many-one reductions, then P = NP. We also show that if there is a sparse NP-complete set under Turing reductions, then the polynomial time hierarchy collapses to Δ2P.

One-way log-tape (1-L) reductions are mappings defined by log-tape Turing machines whose read head on the input can only move to the right. The 1-L reductions provide a more refined tool for studying the feasible complexity classes than the P-time [2,7] or log-tape [4] reductions. Although the 1-L computations are provably weaker than the feasible classes L, NL, P and NP, the known complete sets for those classes are complete under 1-L reductions. However, using known techniques of counting arguments and recursion theory we show that certain log-tape reductions cannot be 1-L and we construct sets that are complete under log-tape reductions but not under 1-L reductions.