The gap between monotone and non-monotone circuit complexity is exponential

DOI10.1007/BF02122563zbMath0807.94026MaRDI QIDQ1813126

Éva Tardos

Publication date: 25 June 1992

Published in: Combinatorica (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)

Related Items (29)

Monotone simulations of non-monotone proofs. ⋮ On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography ⋮ Valiant's holant theorem and matchgate tensors ⋮ Applications of matrix methods to the theory of lower bounds in computational complexity ⋮ A lower bound for intuitionistic logic ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ On derandomization and average-case complexity of monotone functions ⋮ Acyclicity programming for sigma-protocols ⋮ On Linear Secret Sharing for Connectivity in Directed Graphs ⋮ Negation-limited circuit complexity of symmetric functions ⋮ A note on the power of majority gates and modular gates ⋮ An axiomatic duality framework for the theta body and related convex corners ⋮ Unnamed Item ⋮ One-way permutations, computational asymmetry and distortion. ⋮ Natural proofs ⋮ A recursion-theoretic characterisation of the positive polynomial-time functions ⋮ Adventures in monotone complexity and TFNP ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ On Negations in Boolean Networks ⋮ On the minimum number of negations leading to super-polynomial savings ⋮ Non-cancellative Boolean circuits: A generalization of monotone boolean circuits ⋮ Notes on Hazard-Free Circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the negation-limited circuit complexity of merging ⋮ An exponential gap with the removal of one negation gate

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds on monotone complexity of the logical permanent
• The monotone circuit complexity of Boolean functions
• The ellipsoid method and its consequences in combinatorial optimization
• On the Shannon capacity of a graph

This page was built for publication: The gap between monotone and non-monotone circuit complexity is exponential