Complexity of Boolean functions over bases with unbounded fan-in gates

DOI10.1016/0020-0190(95)00182-4MaRDI QIDQ1350754zbMATH OpenOpenAlexFDO

Authors Vlado Dančík

Publication date 27 February 1997

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

Full work available at URL https://doi.org/10.1016/0020-0190(95)00182-4

zbMATH Keywords

Boolean functionsComputational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Recommendations

• On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
• On the multiplicative complexity of Boolean functions over the basis (\(\land,\oplus,1)\).
• Multilevel representation and complexity of circuits of unbounded fan-in gates
• On the multiplicative complexity of Boolean functions
• The generalized complexity of linear Boolean functions

Cited in

(10)

• The complexity of the parity function in unbounded fan-in, unbounded depth circuits
• Topological aspects of Boolean functions
• Multilevel representation and complexity of circuits of unbounded fan-in gates
• On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
• The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
• Ways of synthesizing binary programs admitting recursive call of procedures
• Asymptotically best method for synthesis of Boolean recursive circuits
• Asymptotically best synthesis methods for reflexive-recursive circuits
• scientific article; zbMATH DE number 7561559 (Why is no real title available?)
• On the extension complexity of polytopes separating subsets of the Boolean cube

This page was built for publication: Complexity of Boolean functions over bases with unbounded fan-in gates

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