scientific article; zbMATH DE number 3999837

zbMath0616.94019MaRDI QIDQ4726174

Alexander E. Andreev

Publication date: 1985

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

lower boundcircuit complexitymonotone functionminimal size monotone Boolean circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Limiting negations in non-deterministic circuits ⋮ Lower bounds on the size of bounded depth circuits over a complete basis with logical addition ⋮ \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice ⋮ A lower bound for read-once-only branching programs ⋮ Entropy of contact circuits and lower bounds on their complexity ⋮ A method for obtaining efficient lower bounds for monotone complexity ⋮ Tradeoffs for language recognition on alternating machines ⋮ On reducibility and symmetry of disjoint NP pairs. ⋮ Lower bounds for depth-restricted branching programs ⋮ On algorithm complexity ⋮ Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\) ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ A simple lower bound for monotone clique using a communication game ⋮ Resolution over linear equations and multilinear proofs ⋮ Reductions for monotone Boolean circuits ⋮ Separating complexity classes related to \(\Omega\)-decision trees ⋮ Natural proofs ⋮ Negation-limited formulas ⋮ Approximation Limitations of Pure Dynamic Programming ⋮ On Negations in Boolean Networks ⋮ On the bottleneck counting argument ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An exponential lower bound for the size of monotone real circuits ⋮ Monotone circuit lower bounds from robust sunflowers ⋮ On the negation-limited circuit complexity of merging