A measure in which Boolean negation is exponentially powerful

DOI10.1016/0020-0190(83)90051-0MaRDI QIDQ790083zbMATHOpenAlexFDO

Authors Sven Skyum

Publication date 1983

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

Full work available at URL https://doi.org/10.1016/0020-0190(83)90051-0

zbMATH Keywords

projectionsBoolean functionscombinatorial complexitycircuit sizeformula sizecomplexity measures for families of Boolean functionsrepresentation size

Mathematics Subject Classification ID

Recommendations

• Measure on Boolean algebras
• Measures on Boolean algebras
• Measures on Boolean Algebras
• Boolean powers and quantum measurements
• Boolean operations over measure algebras
• On various nonlinearity measures for Boolean functions
• scientific article; zbMATH DE number 7310064
• Bases of measurability in Boolean algebras
• A strong log-concavity property for measures on Boolean algebras
• scientific article; zbMATH DE number 1529761

Cites work

• A complexity theory based on Boolean algebra
• The complexity of monotone boolean functions

Cited in

(2)

• Threshold circuits of bounded depth
• On convex complexity measures

This page was built for publication: A measure in which Boolean negation is exponentially powerful

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