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

DOI10.1016/0020-0190(95)00182-4zbMath0875.68790OpenAlexW1995176744MaRDI QIDQ1350754

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)

Related Items (6)

Asymptotically best synthesis methods for reflexive-recursive circuits ⋮ On the extension complexity of polytopes separating subsets of the Boolean cube ⋮ Unnamed Item ⋮ Ways of synthesizing binary programs admitting recursive call of procedures ⋮ Asymptotically best method for synthesis of Boolean recursive circuits ⋮ On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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