Разделительная декомпозиция отношений в задачах многокритериального выбора

Исследуются алгоритмические проблемы, связанные с разделительной декомпозицией отношений в задачах многокритериального выбора, т.е. с возможностью разбиения множества критериев $I$ на подмножества $I_1,\dots,I_k$ и представления выбора по заданному отношению $\rho$ на $I$ в виде последовательного выбора по некоторым отношениям $\rho_1,\dots,\rho_k$, заданным соответственно на $I_1,\dots,I_k$. Отношения предполагаются порядковыми и описываются функциями $(3,2)$-значной логики. Доказывается, что всякое отношение обладает лучшей разделительной декомпозицией, которая единственна с точностью до некоторого преобразования. При задании представляющих функций отношений в форме ДНФ и КНФ задачи о существовании нетривиальных декомпозиций и о построении лучших декомпозиций NP-трудны. Если отношения обладают свойством монотонности, то в случае ДНФ эти задачи остаются NP-трудными, а при задании в виде КНФ полиномиально разрешимы. Библиогр. 13.