On the Inversion Complexity of a System of Functions
From MaRDI portal
Publication:3254629
DOI10.1145/320941.320945zbMath0085.11601OpenAlexW2119024968MaRDI QIDQ3254629
Publication date: 1958
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/320941.320945
Related Items (26)
Limiting negations in non-deterministic circuits ⋮ Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography ⋮ Limiting negations in bounded-depth circuits: an extension of Markov's theorem ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ Improvement of nonmonotone complexity estimates of \(k\)-valued logic functions ⋮ Unnamed Item ⋮ Cyclic Boolean circuits ⋮ Bounded queries to SAT and the Boolean hierarchy ⋮ ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS ⋮ Negation-limited circuit complexity of symmetric functions ⋮ The minimum number of negations in circuits for systems of multi-valued functions ⋮ On the mystery of negations in circuits: structure vs power ⋮ A curious new result in switching theory ⋮ Characteristic measures of switching functions ⋮ New bounds for energy complexity of Boolean functions ⋮ Negation-limited formulas ⋮ Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences ⋮ Negation-limited complexity of parity and inverters ⋮ On Negations in Boolean Networks ⋮ On the minimum number of negations leading to super-polynomial savings ⋮ The learnability of exclusive-or expansions based on monotone DNF formulas ⋮ Unnamed Item ⋮ On the negation-limited circuit complexity of merging ⋮ On the positive and the inversion complexity of Boolean functions ⋮ An exponential gap with the removal of one negation gate
This page was built for publication: On the Inversion Complexity of a System of Functions
