О сложности проблемы разрешимости систем уравнений над конечными частичными порядками

Классическая алгебраическая геометрия изучает множества решений алгебраических уравнений над полями вещественных и комплексных чисел. В рамках вычислительной алгебраической геометрии предложены алгоритмы (например, алгоритм Бухбергера) для решения систем полиномиальных уравнений над этими полями. Универсальная алгебраическая геометрия изучает системы уравнений над произвольными алгебраическими системами. Под уравнениями понимаются атомарные формулы языка алгебраической системы. В работе рассматривается проблема распознавания разрешимости систем уравнений над конечными частично упорядоченными множествами. Доказывается, что эта проблема является NP-полной в случае, когда проверяется существование решения, состоящего из попарно различных элементов частично упорядоченного множества.