On the negation-limited circuit complexity of merging
From MaRDI portal
Publication:1861565
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)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Limiting negations in non-deterministic circuits, Reductions for monotone Boolean circuits, Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences, Negation-limited complexity of parity and inverters, Limiting negations in bounded-depth circuits: an extension of Markov's theorem
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item