There are no p-complete families of symmetric Boolean functions

DOI10.1016/0020-0190(89)90174-9zbMath0662.94023OpenAlexW2002125674MaRDI QIDQ1114662

Mihály Geréb-Graus, Ramamohan Paturi

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

completenesssymmetric Boolean functionsp-complete familyp-projection

Mathematics Subject Classification ID

Related Items (1)

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

Cites Work

• A complexity theory based on Boolean algebra
• Unnamed Item

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