A measure in which Boolean negation is exponentially powerful

DOI10.1016/0020-0190(83)90051-0zbMath0533.94004OpenAlexW2062322643MaRDI QIDQ790083

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

Related Items

Threshold circuits of bounded depth

Cites Work

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