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

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