Abstract:
The number of incomparable $k$-dimensional intervals in the Boolean $n$-cube is estimated. The result is used to estimate the complexity of approximate computation of an arbitrary monotone Boolean function of $n$ variables.
Key words:monotone Boolean function, complexity of approximate computation, incomparable intervals.