Нижняя оценка сложности информационных сетей для одного отношения частичного порядка

В статье исследуются задачи поиска, в которых отношение поиска является отношением частичного порядка. Доказано общее свойство таких задач, названное фактом существования главных цепей. С помощью этого свойства для задач поиска с естественным отношением частичного порядка, заданным на булевом кубе, получена нижняя оценка. Доказано существование таких задач с данным отношением поиска, для которых полученная нижняя оценка асимптотически неулучшаема.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, грант 95–01–00597.