Abstract.

Let $\Omega$ be the basis consisting of a negation and logical `and' and `or' operations over any number of inputs. Every Boolean function of $n$ variables can be realised by a Boolean circuit over $\Omega$ using at most $2.122\cdot 2^{n/2}+n+1$ gates ($2\cdot 2^{n/2}+n+1$ for even $n$). We also show that almost all Boolean functions have circuit complexity at least $1.914\cdot 2^{n/2}-4n$.

Keywords: boolean functions, computational complexity

Bibtex entry:

@Article{Dan96,
  author =       "Vlado Dan{\v c}{\'\i}k",
  title =        "Complexity of Boolean functions over bases with
                  unbounded fan-in gates",
  journal =      "Information Processing Letters",
  year =         "1996",
  number =       "1",
  volume =       "57", 
  pages  =       "31-34" 
}

Return to Previous Level

USC Computational Biology Home Page