There are no p-complete families of symmetric Boolean functions

DOI10.1016/0020-0190(89)90174-9MaRDI QIDQ1114662zbMATH OpenOpenAlexFDO

Authors Mihály Geréb-Graus, Ramamohan Paturi, Endre Szemerédi

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90174-9

zbMATH Keywords

completenessp-complete familyp-projectionsymmetric Boolean functions

Mathematics Subject Classification ID

Review text

We present a proof of a negative answer to the question raised by \textit{S. Skyum} and \textit{L. G. Valiant} [22nd Ann. IEEE Symp. on Foundations of Computer Science, New York, 244-253 (1981)], namely, whether the class of symmetric Boolean functions has a p-complete family.

Recommendations

• scientific article; zbMATH DE number 4035741
• Bounded-depth, polynomial-size circuits for symmetric functions
• Lower bounds to the complexity of symmetric Boolean functions
• scientific article; zbMATH DE number 18630
• scientific article; zbMATH DE number 919269

Cites work

• A complexity theory based on Boolean algebra
• scientific article; zbMATH DE number 3744549 (Why is no real title available?)

Cited in

(1)

• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)

This page was built for publication: There are no p-complete families of symmetric Boolean functions

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