ИСТИНА

Работа посвящена вопросу сложности восстановления частичного порядка на конечном множестве, если известно, что частичный порядок обладает какими-то наперед заданными свойствами. Рассматривается модель вычислений в которой под сложностью понимается количество сравнений, необходимое для восстановления частичного порядка. Исследуются классы частично упорядоченных множеств, для которых задача восстановления порядка решается меньше чем за квадратичное число сравнений относительно количества элементов в множестве.