О сложности проблемы равенства в полугруппах с условием однородности определяющих соотношений
Ключевые слова:
полугруппы, проблема равенства, вычислительная сложностьАннотация
В данной работе изучается вычислительная сложность проблемы равенства полугрупп
с условием однородности определяющих соотношений. Это конечно определенные полугруппы,
в которых для каждого определяющего соотношения длины левой и правой частей равны. Проблема равенства в таких полугруппах разрешима, но известные алгоритмы работают за экспоненциальное время (и пространство).
В данной статье доказывается, что проблема равенства в любой
полугруппе с условием однородности определяющих соотношений лежит в классе PSPACE, который
состоит из алгоритмических проблем распознавания, которые решаются машинами
Тьюринга с использованием пространства (ячеек памяти), ограниченного полиномиально.
Тем самым улучшается верхняя оценка на вычислительную сложность по пространству.
С другой стороны, доказывается, что cуществует полугруппа с условием однородности определяющих соотношений,
в которой проблема равенства полна в классе PSPACE относительно полиномиальной сводимости.
Предполагается (хотя и не доказано), что класс PSPACE шире класса NP и тем более класса P.
Таким образом, показано, что существуют полугруппы с условием однородности определяющих соотношений
с трудноразрешимой проблемой равенства.
