Publication:4092993
From MaRDI portal
zbMath0327.68055MaRDI QIDQ4092993
Publication date: 1975
68Q25: Analysis of algorithms and problem complexity
Related Items
On the Complexity of Multivalued Logic Functions over Some Infinite Basis, ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS, Negation-limited circuit complexity of symmetric functions, Negation-limited formulas, Limiting negations in non-deterministic circuits, Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences, On the minimum number of negations leading to super-polynomial savings, Negation can be exponentially powerful, An exponential gap with the removal of one negation gate, Asymptotics of growth for non-monotone complexity of multi-valued logic function systems, The minimum number of negations in circuits for systems of multi-valued functions, On the negation-limited circuit complexity of merging, On the mystery of negations in circuits: structure vs power, Exact value of the nonmonotone complexity of Boolean functions, Limiting negations in bounded-depth circuits: an extension of Markov's theorem, On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography, On Negations in Boolean Networks