Monotone real circuits are more powerful than monotone Boolean circuits

DOI10.1016/S0020-0190(97)00007-0MaRDI QIDQ290209zbMATH OpenOpenAlexFDO

Authors Arnold Rosenbloom

Publication date 1 June 2016

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

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00007-0

zbMATH Keywords

computational complexityBoolean circuitscircuit complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A note on monotone real circuits
• An exponential lower bound for the size of monotone real circuits
• Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes
• Threshold functions and bounded depth monotone circuits
• The monotone circuit complexity of Boolean functions

Cites work

• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 1261805 (Why is no real title available?)
• scientific article; zbMATH DE number 1263234 (Why is no real title available?)
• scientific article; zbMATH DE number 1142303 (Why is no real title available?)
• The monotone circuit complexity of Boolean functions

Cited in

(7)

• Representations of monotone Boolean functions by linear programs
• On the minimum number of negations leading to super-polynomial savings
• Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes
• Combinatorics of monotone computations
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Discretely ordered modules as a first-order extension of the cutting planes proof system
• A note on monotone real circuits

This page was built for publication: Monotone real circuits are more powerful than monotone Boolean circuits

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