A lower bound for the complexity of information networks for a partial ordering relation

We study the search problems where the search relation is a partial order relation. We reveal the common property of these problems called the existence of principal chains. Using this property, we obtain a lower bound for the complexity of the search problems with the natural partial order relation given on the Boolean cube, and prove that the lower bound is asymptotically attainable.
This work was supported by the Russian Foundation for Basic Research, grant 95–01–00597.