• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Об оценках сложности схем в одном бесконечном базисе

С. 97-100.
We study Boolean circuit complexity in an infinite basis consisting of all Boolean functions that equal 1 only on sets of pair-wise incomparable tuples. It is known that lower bounds on the complexity of linear function, majority function and almost all boolean functions of $n$ variables are of the order $\sqrt n.$ We show that the complexity of any $n$-variable Boolean function is at most $n$ in this basis.