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

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

С. 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.