# A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas - Computer Science > Computational Complexity

A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas - Computer Science > Computational Complexity - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: In this note, we consider the minimum number of NOT operators in a Booleanformula representing a Boolean function. In circuit complexity theory, theminimum number of NOT gates in a Boolean circuit computing a Boolean function\$f\$ is called the inversion complexity of \$f\$. In 1958, Markov determined theinversion complexity of every Boolean function and particularly proved that\$\lceil \log 2n+1 ceil\$ NOT gates are sufficient to compute any Booleanfunction on \$n\$ variables. As far as we know, no result is known for inversioncomplexity in Boolean formulas, i.e., the minimum number of NOT operators in aBoolean formula representing a Boolean function. The aim of this note isshowing that we can determine the inversion complexity of every Booleanfunction in Boolean formulas by arguments based on the study of circuitcomplexity.

Autor: Hiroki Morizumi

Fuente: https://arxiv.org/

DESCARGAR PDF