The complexity of sparse sets in P. (English) Zbl 0608.68035

Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 1-11 (1986).
[For the entire collection see Zbl 0591.00015.]
A set is P-printable iff there is a polynomial-time function which, over input \(1^ n\), prints out the elements of S which have length \(\leq n\). In this preliminary report the author presents new characterizations of P-printable sets. He also gives new necessary and sufficient conditions for the existence of sparse sets is P which are not P-printable. These results are shown to be related to several problems on P-uniform circuit complexity, and one-way functions.
Reviewer: D.Mundici


68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)


Zbl 0591.00015