A counterexample to a conjecture of Schnorr referring to monotone networks

DOI10.1016/0304-3975(79)90012-4zbMath0401.94040OpenAlexW1964868004WikidataQ122965856 ScholiaQ122965856MaRDI QIDQ1255472

Ingo Wegener

Publication date: 1979

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(79)90012-4

zbMATH Keywords

ComplexityPrime ImplicantsMonotone Boolean FunctionMonotone Networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Switching functions whose monotone complexity is nearly quadratic
• A lower bound on the number of additions in monotone computations