Том 9, серия 1, номер 4 , 2002 г., Стр. 82-105

УДК 519.95
Л. А. Шоломов
Сложность распознавания свойств порядковых отношений в $n$-мерных пространствах

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

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

Статья поступила 24 июня 2002 г.