scientific article; zbMATH DE number 3984573

From MaRDI portal
Publication:3747725





[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.




Cited in
(32)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3747725)