A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas

Details A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas

2008-11-05

arxiv.org/abs/0811.0699v1

Computer Science

Computational Complexity

5 pages, 1 figures

Scientific paper

In this note, we consider the minimum number of NOT operators in a Boolean formula representing a Boolean function. In circuit complexity theory, the minimum number of NOT gates in a Boolean circuit computing a Boolean function $f$ is called the inversion complexity of $f$. In 1958, Markov determined the inversion complexity of every Boolean function and particularly proved that $\lceil \log_2(n+1) \rceil$ NOT gates are sufficient to compute any Boolean function on $n$ variables. As far as we know, no result is known for inversion complexity in Boolean formulas, i.e., the minimum number of NOT operators in a Boolean formula representing a Boolean function. The aim of this note is showing that we can determine the inversion complexity of every Boolean function in Boolean formulas by arguments based on the study of circuit complexity.

Affiliated with

Also associated with

No associations

Rating

A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-373337