On the Inversion Complexity of a System of Functions

DOI10.1145/320941.320945MaRDI QIDQ3254629zbMATH OpenOpenAlexFDO

Authors A. A. jun. Markoff

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

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Recommendations

• scientific article; zbMATH DE number 1880324
• On inverse operations and their descriptional complexity
• scientific article; zbMATH DE number 6415494
• scientific article; zbMATH DE number 1553331
• Structural analysis of the complexity of inverse functions
• scientific article; zbMATH DE number 1962830
• On the positive and the inversion complexity of Boolean functions

Cited in

(30)

• Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences
• Negation-limited complexity of parity and inverters
• On the minimum number of negations leading to super-polynomial savings
• Bounded queries to SAT and the Boolean hierarchy
• Characteristic measures of switching functions
• The learnability of exclusive-or expansions based on monotone DNF formulas
• An exponential gap with the removal of one negation gate
• 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
• Limiting negations in bounded-depth circuits: an extension of Markov's theorem
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Lower bounds for Boolean circuits of bounded negation width
• On the positive and the inversion complexity of Boolean functions
• On negation complexity of injections, surjections and collision-resistance in cryptography
• On Negations in Boolean Networks
• Cyclic Boolean circuits
• Testing k-monotonicity
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS
• A curious new result in switching theory
• New bounds for energy complexity of Boolean functions
• Improvement of nonmonotone complexity estimates of k-valued logic functions
• Negation-limited circuit complexity of symmetric functions
• On saving energy in Boolean circuits via negations
• On exact learning of d-monotone functions
• Decision tree complexity versus block sensitivity and degree
• The exact circuit complexity of Boolean functions in an infinite basis
• Negation-limited formulas
• Limiting negations in non-deterministic circuits

This page was built for publication: On the Inversion Complexity of a System of Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3254629)