О сложности задач минимизации и сжатия моделей последовательного выбора

Модель последовательного выбора глубины $k$ по бинарным отношениям $r_1,r_2,\dots,r_k$ на множестве вариантов $A$ каждому $X\subseteq A$ ставит в соответствие его подмножество $C_{r_k}(\ldots C_{r_2}(C_{r_1}(X))\ldots)$, где $C_r(Y)=\{y\in Y|(\forall z\in Y)z\bar ry\}$, $Y\subseteq A$. Задача минимизации состоит в том, чтобы построить эквивалентную модель наименьшей глубины; задача сжатия ставится аналогично, но построенная модель должна удовлетворять некоторому условию “вложенности”. Доказывается, что при $k\geqslant 3$ задача минимизации и задача сжатия моделей глубины $k$ являются NP-трудными (при $k=2$ они полиномиальны). Исследуются параметры локальных алгоритмов решения этих задач и устанавливается, что задача сжатия разрешима алгоритмами, работающими с окрестностями размера 3, задача минимизации не разрешима ни при каком конечном размере окрестностей. При произвольном $k$ построена модель глубины $k$, минимизация которой не может быть проведена на основе рассмотрения окрестностей, отличных от всей модели. Ил. 2, библиогр. 12.