Abstract
P-printable sets, defined in [HY-84], arise naturally in the study of P-uniform circuit complexity, generalized Kolmogorov complexity, and data compression, as well as in many other areas. We present new characterizations of the P-printable sets and present necessary and sufficient conditions for the existence of sparse sets in P which are not P-printable. The complexity of sparse sets in P is shown to be central to certain questions about circuit complexity classes and about one-way functions. Among the main results are:
(1) There is a sparse set in P which is not P-printable iff
There is a sparse set in DLOG which is not P-printable iff
There is a sparse set in FNP — P
(where FNP is a class related to U: FNP=the class of sets accepted by nondeterministic polynomial-time Turing machines which accept inputs of size n with nO(1) accepting computations; FNP stands for NP with “few” accepting computations).
(2) A set S is P-printable iff
S is sparse and S is accepted by a one-way logspace-bounded AuxPDA.
(3) NC=PUNC iff
All P-printable sets in P are in NC iff
All Tally languages in P are in NC.