The gap between monotone and non-monotone circuit complexity is exponential
From MaRDI portal
Publication:1813126
DOI10.1007/BF02122563zbMath0807.94026MaRDI QIDQ1813126
Publication date: 25 June 1992
Published in: Combinatorica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)
Related Items
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
