On the negation-limited circuit complexity of merging

DOI10.1016/S0166-218X(02)00215-9zbMath1011.68040MaRDI QIDQ1861565

Kazuyuki Amano, Akira Maruoka, Jun Tarui

Publication date: 9 March 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

negation-limited circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Limiting negations in non-deterministic circuits ⋮ Limiting negations in bounded-depth circuits: an extension of Markov's theorem ⋮ Reductions for monotone Boolean circuits ⋮ Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences ⋮ Negation-limited complexity of parity and inverters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• The monotone circuit complexity of Boolean functions
• The gap between monotone and non-monotone circuit complexity is exponential
• On the Inversion Complexity of a System of Functions
• On the Complexity of Negation-Limited Boolean Networks

This page was built for publication: On the negation-limited circuit complexity of merging