Том 6, серия 1, номер 3, 1999 г., Стр. 87-109

УДК 519.816
Л. А. Шоломов
О сложности задач минимизации и сжатия моделей последовательного выбора

Аннотация:
Модель последовательного выбора глубины $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.

Шоломов Л. А. ¹
1. Институт системного анализа РАН,
пр. 60-летия Октября, 9, 117312 Москва, Россия
е-mail: sholomov@cs.isa.ac.ru

Статья поступила 22 февраля 1999 г.