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

Allender, Eric W.

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

MSC:

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

Keywords:

polynomial time; tally language; NC; DLOG; FNP; P-printable sets; sparse sets is P; P-uniform circuit complexity; one-way functions

Citations:

Zbl 0591.00015