RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., сер. 1, 2002, том 9, выпуск 4, страницы 82–105 (Mi da188)

Эта публикация цитируется в 3 статьях

Сложность распознавания свойств порядковых отношений в $n$-мерных пространствах

Л. А. Шоломов

Институт системного анализа РАН

Аннотация: Рассматриваются бинарные отношения в $n$-мерном пространстве, являющиеся порядковыми, т.е. зависящими для каждой пары точек пространства лишь от соотношений ($>$, $<$, $=$) одноименных компонент. Они могут быть представлены булевыми функциями от покомпонентных соотношений. Исследуются на NP-трудность и полиномиальность по представляющим булевым функциям задачи распознавания отношения на транзитивность, ацикличность, полноту и др. Получено решение этих задач для всех основных свойств отношений при задании представляющих функций посредством дизъюнктивных и конъюнктивных нормальных форм.
Табл. 1, ил. 1, библиогр. 6.

УДК: 519.95

Статья поступила: 24.06.2002



Реферативные базы данных:


© МИАН, 2024