\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}

\def\udcs{510.652} %Здесь автор определяет УДК своей работы
\def\mscs{11U99} %Здесь автор определяет классификаторы AMS своей работы
%\setcounter{page}{144}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 11, стр. 144--144 (2014) \hspace{65mm}{\rm\small УДК \udcs}}
     \newline
         \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}

\thispagestyle{empty}

\title[О сложности проблемы равенства в полугруппах]{О сложности проблемы равенства в полугруппах с условием однородности определяющих соотношений}
\author{{А.Н. РЫБАЛОВ}}%
\address{Alexander Nikolaevich Rybalov  %Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} prospekt Koptyuga 4,
\newline\hphantom{iii} Novosibirsk, 630090, Russia.
\newline\hphantom{iii} Pevtsova 13,
\newline\hphantom{iii} Omsk, 644099, Russia.
}%

\email{alexander.rybalov@gmail.com}%

\thanks{\sc Rybalov, A.N., On complexity of the word problem in semigroups with homogeneous relations}
\thanks{\copyright \ 2023 Рыбалов А.Н.}
\thanks{\rm Работа выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022-0003.}
\thanks{\it Поступила 30 июня 2023 г., опубликована 1 сентября 2023 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. }
In this paper we study the computational complexity of the word problem in semigroups
with the condition of homogeneity of the defining relations. These are finitely defined semigroups,
in which for each defining relation the lengths of the left and right parts are equal.
The word problem for such semigroups is decidable, but known algorithms require exponential time and memory.
We prove that this problem belongs to the class {\bf PSPACE}, 
consisting of algorithmic problems that are solved by Turing machines
using space (memory cells) bounded polynomially.
This improves the upper bound on the space complexity known before.
On the other hand, we prove that there exists a semigroup with the condition of homogeneity of defining relations,
in which the equality problem is complete in the class {\bf PSPACE} with respect to polynomial reducibility.
It is assumed (although not proven) that the class {\bf PSPACE} is wider than the class {\bf NP} and, even more so, the class {\bf P}.
Thus, it is shown that there are semigroups with the condition of homogeneity of defining relations
with the intractable problem of equality.
\medskip

\noindent{\bf Keywords:} computational complexity, semigroups, word problem.
 \end{quote}
}



\section{Введение}

Важнейшей алгоритмической проблемой в алгебре является проблема равенства для различных алгебраических
систем: групп, полугрупп, колец, алгебр и т.д. Одним из выдающихся достижений алгебры ХХ века является
построение А.~А.~Марковым \cite{Markov}, Э.~Постом \cite{Post} конечно определенных полугрупп и 
П.~С.~Новиковым \cite{Novik} конечно определенных групп с неразрешимой проблемой равенства. 
К ярким положительным результатам можно отнести результат А.~И.~Мальцева \cite{Malcev} о разрешимости
проблемы равенства в любой конечно определенной коммутативной полугруппе.

В дальнейшем, фокус исследований проблемы равенства в полугруппах сдвинулся в сторону изучения ее
вычислительной сложности для различных классов полугрупп с разрешимой проблемой равенства.
Е.~Кордоза показал \cite{Cor}, что проблема равенства в любой фиксированной 
конечно определенной коммутативной полугруппе
разрешима за линейное время. С другой стороны, Е.~Майр и А.~Мейер доказали \cite{MM}, что проблема равенства
в многообразии всех коммутативных полугрупп (то есть, когда входом алгоритма является не только два
слова, для которых проверяется равенство, но и само конечное представление полугруппы) является
полной относительной полиномиальной сводимости в классе {\bf EXPSPACE}. Класс {\bf EXPSPACE} --
это класс проблем, разрешимых с использованием экспоненциальной памяти. 
Доказано (см., например, \cite{GJ}), что этот класс строго шире класса {\bf P}.

В данной работе изучается вычислительная сложность проблемы равенства полугрупп 
с условием однородности определяющих соотношений. Это конечно определенные полугруппы,
в которых для каждого определяющего соотношения длины левой и правой частей равны.
Сам термин был предложен в известном обзоре С.~И.~Адяна и В.~Г.~Дурнева \cite{AD},
где буквально в одном абзаце доказывается разрешимость проблемы равенства для таких полугрупп.
Частным случаем таких полугрупп являются так называемые моноиды трассировки \cite{DM} или частично коммутативные
моноиды, которые возникают в информатике при анализе распараллеливания программ.
Известно \cite{DM}, что проблема равенства в таких моноидах решается за линейное время.
Однако в общем случае, известные алгоритмы для решения проблемы равенства в полугруппах 
с условием однородности определяющих соотношений (например, алгоритм из \cite{AD}),
работают за экспоненциальное время (и пространство). 

В данной статье доказывается, что проблема равенства в любой 
полугруппе с условием однородности определяющих соотношений лежит в классе {\bf PSPACE}.
Здесь класс {\bf PSPACE} состоит из алгоритмических проблем распознавания, которые решаются машинами
Тьюринга с использованием пространства (ячеек памяти), ограниченного полиномиально.
Тем самым улучшается верхняя оценка на вычислительную сложность по пространству из \cite{AD}.
С другой стороны, доказывается, что cуществует полугруппа с условием однородности определяющих соотношений,
в которой проблема равенства полна в классе {\bf PSPACE} относительно полиномиальной сводимости.
Предполагается (хотя и не доказано), что класс {\bf PSPACE} шире класса {\bf NP} и тем более класса {\bf P}.
Таким образом, показано, что существуют полугруппы с условием однородности определяющих соотношений
с трудноразрешимой проблемой равенства.


\section{Предварительные сведения}

Пусть $S = \langle a_1, \ldots, a_n\ |\ u_1 = v_1, \ldots, u_m = v_m \rangle$ -- конечно определенная
полугруппа с множеством порождающих $A = \{ a_1, \ldots, a_n \}$ и множеством определяющих соотношений
$R = \{ u_1 = v_1, \ldots, u_m = v_m \}$. Полугруппа $S$ называется {\em полугруппой с условием 
однородности определяющих соотношений}, если $|u_i| = |v_i|$ для каждого $i=1,\ldots,m$.

Пусть $M$ -- машина Тьюринга, $s_M(x)$ -- число ячеек ленты, используемое в работе $M$ на $x$. 
Проблема распознавания (множество) $A$ принадлежит {\em классу} {\bf PSPACE}, если существует
машина Тьюринга $M$, распознающая $A$, и полином $p(n)$ такие, что $s_M(x) < p(|x|)$.

Проблема распознавания (множество) $A$ {\bf PSPACE}-{\em полна}, если
\begin{enumerate}
\item $A \in \text{\bf PSPACE}$,
\item любая проблема $B$ из {\bf PSPACE} полиномиально сводится к $A$, то есть 
существует функция $f$, вычислимая за полиномиальное время, такая, что
$$
\forall x\ x \in B \Leftrightarrow f(x) \in B.
$$
\end{enumerate}
Известно (см., например, \cite{GJ}), что {\bf PSPACE}-полные проблемы существуют.

Проблема $A$ принадлежит {\em классу} {\bf NPSPACE}, если существует
недетерминированная машина Тьюринга $M$ и полином $p(n)$ такие, что
$x \in A$ $\Leftrightarrow$ $\exists$ вычислительный путь $\tau$ $M$ на $x$ такой, что 
$M_{\tau}(x)=1$ и $s_M(\tau,x) < p(|x|)$. Строгое определение недетерминированной машины
Тьюринга можно найти в \cite{GJ}. В программе таких машин могут быть пары правил с одинаковыми
левыми частями (внутренним состоянием и символом, обозреваемым в данный момент кареткой).
Предполагается, что при работе такой машины в определенный момент может быть выбрано и то и другое правило.
Таким образом, на одном входе могут возникнуть несколько вычислительных путей, и, в итоге,
несколько результатов работы машины.

В теории сложности вычислений хорошо известна теорема Сэвича \cite{Sav}, которая утверждает, 
что {\bf PSPACE} = {\bf NPSPACE}. Это означает, что для любой проблемы, распознаваемой
недерминированным алгоритмом с полиномиально ограниченной памятью, можно
построить детерминированный алгоритм также с полиномиально ограниченной памятью,
который также решает эту проблему. Теорема Сэвича контрастирует с ситуацией с аналогичными
классами для временной сложности {\bf P} и {\bf NP} -- большинство исследователей считает, что
эти классы различаются.

\section{Основные результаты}

В доказательстве следующей теоремы мы будем использовать модель машин Тьюринга с несколькими рабочими лентами.
Эта модель полиномиально эквивалентна обычной модели с одной лентой (см. \cite{GJ}), и является более удобной
для описания конкретных алгоритмов.

\begin{theorem} \label{pspace}
Проблема равенства в любой полугруппе с условием однородности определяющих соотношений
принадлежит классу {\bf PSPACE}.
\end{theorem}
\begin{proof} 
Пусть $S = \langle a_1, \ldots, a_n\ |\ u_1 = v_1, \ldots, u_m = v_m \rangle$ -- конечно определенная
полугруппа с условием однородности определяющих соотношений. Докажем, что проблема равенства в $S$
принадлежит классу {\bf NPSPACE}. Из этого, по теореме Сэвича, будет следовать ее принадлежность 
классу {\bf PSPACE}.

Опишем работу следующего недетерминированного алгоритма $\mathcal{A}$ с полиномиально ограниченной памятью.
Заметим сначала очевидный факт: при замене в слове $w$ согласно определяющим соотношениям $S$ может 
получиться слово $w^{\prime}$ для которого $|w| = |w^{\prime}|$.
Пусть на входе имеются два слова $(w_1,w_2)$ над алфавитом $A$.
Алгоритм $\mathcal{A}$ работает на входе $(w_1,w_2)$ следующим образом. 
\begin{enumerate}
\item Вначале на первой ленте записано слово $w^{\prime} = w_1$, на второй -- слово $w_2$.
\item Если длины $w_1$ и $w_2$ не равны, выдает ответ <<НЕТ>>. Иначе переходит на следующий шаг.
\item Недетерминированно выбирает в слове $w^{\prime}$ подслово, совпадающее с левой или правой частью какого-то соотношения полугруппы $S$, и заменяет его согласно этому соотношению. Получается новое слово $w^{\prime}$.
Заметим, что длина нового слова осталась той же самой, тем самым алгоритм не использовал
 новую память для вычислений.
\item Если $w^{\prime} = w_2$, то останавливается и выдает ответ <<ДА>>.
\item Иначе возвращается на шаг 3.
\end{enumerate}
Легко видеть, что, $w_1 = w_2$ в полугруппе $S$, то есть слово $w_2$ можно получить из $w_1$ применением
замен согласно определяющим соотношениям $S$, тогда и только тогда, когда существует вычислительный 
путь алгоритма $\mathcal{A}$ на $(w_1, w_2)$, на котором он выдает ответ <<ДА>>.
Полиномиальное ограничение на память при работе алгоритма $\mathcal{A}$ следует из замечания к шагу 3.
\end{proof}

В доказательстве следующей теоремы мы будем использовать 
стандартную модель машин Тьюринга с одной рабочей лентой.
У таких машин будут два конечных состояния: $q_a$ -- принимающее и $q_r$ -- отвергающее.

\begin{theorem} 
Существует полугруппа с условием однородности определяющих соотношений, для которой
проблема равенства является {\bf PSPACE}-полной.
\end{theorem}
\begin{proof} 
Пусть $C \subseteq A^{\ast}$ -- некоторое {\bf PSPACE}-полное подмножество строк над алфавитом
$A = \{ a_1, \ldots, a_k \}$. Пусть $M$ -- машина Тьюринга, распознающая множество $C$ с рабочим
алфавитом $A \cup \{ a_0 \}$, где $a_0$ будет обозначать пустой символ. Обозначим через $p(n)$ полином,
ограничивающий функцию пространства $s_M(x)$ машины $M$. Наконец пусть 
$Q = \{ q_1, q_2, \ldots, q_m, q_a, q_r \}$ -- множество состояний машины $M$, среди которых отдельно
выделены два конечных состояния: $q_a$ -- принимающее и $q_r$ -- отвергающее состояния.
Программа машины $M$ состоит из правил вида
$$
(q_i, a) \rightarrow (q_j,b,shift),
$$
где $q_i \in Q \setminus \{ q_a, q_r \}$, $q_j \in Q$, $a,b \in A \cup \{ a_0 \}$
и $shift \in \{ R, L \}$ -- сдвиг каретки. По одному правилу для каждой возможной комбинации $(q_i,a)$.

Будем строить полугруппу $S$ с условием однородности определяющих соотношений, определяющие соотношения
которой будут соответствовать правилам программы машины $M$, а цепочка преобразований согласно этим
соотношениям некоторого начального слова будет моделировать работу машины $M$ на входном слове $w \in A^{\ast}$
до ее остановки с условием ограничения $p(|w|)$ на используемое пространство.

Порождающими полугруппы $S$ будет множество $X = A \cup \{ a_0 \} \cup Q$. Теперь
каждому правилу программы машины $M$ вида
$$
(q_i, a) \rightarrow (q_j,b,R)
$$
сопоставим определяющее соотношение $q_i a = b q_j$, а каждому правилу вида
$$
(q_i, a) \rightarrow (q_j,b,L)
$$
сопоставим определяющие соотношения $c q_i a = q_j c b$ для всех $c \in A \cup \{ a_0 \}$.
Добавим еще соотношения $q_a c = q_a a_0$ и $q_a c = c q_a$ для всех символов $c \in A \cup \{ a_0 \}$.
Легко заметить, что правые и левые части всех этих соотношений имеют одинаковые длины, то есть
полугруппа $S$ получается с условием однородности определяющих соотношений.

Покажем теперь, что машина $M$ работает на слове $w \in A^{\ast}$, останавливается и принимает слово $w$
(то есть попадает в состояние $q_a$), используя при этом пространство, ограниченное $p(|w|)$, тогда и
только тогда, когда в полугруппе $S$ равны слова $w_1 = a_0^{p(|w|)} q_1 w a_0^{p(|w|)}$ и 
$w_2 = q_a a_0^{2p(|w|)+|w|}$. Заметим, что $|w_1| = |w_2| = 2p(|w|)+|w|+1$.

Действительно, пусть машина $M$ принимает вход $w$. Тогда, нетрудно видеть, что каждой конфигурации
машины $M$ (то есть содержимому ленты, положению каретки и состоянию машины $M$), которая получается
применением некоторого правила программы, соответствует слово, которое получается применением соответствующего
определяющего соотношения. В частности, начальной конфигурации машины соответствует слово 
$w_1 = a_0^{p(|w|)} q_1 w a_0^{p(|w|)}$.
При этом те пустые ячейки ленты, которые пока не задействованы в вычислении, но,
потенциально могут использоваться в будущем, в словах-элементах полугруппы $S$ уже заранее <<зарезервированы>>
в начале и в конце слова в символах $a_0$.
Причем, условие, что количество ячеек ленты, используемое в работе, ограничено $p(|w|)$, гарантирует, что
этих зарезервированных символов $a_0$ хватит для корректного моделирования работы машины.

После того, как машина $M$ попадает в конечное состояние $q_a$ и принимает вход $w$, 
в слове-элементе полугруппы $S$, соответствующем этой конфигурации, появляется буква $q_a$.
С помощью соответствующих определяющих соотношений для $q_a$ слово можно преобразовать в 
$w_2 = q_a a_0^{2p(|w|)+|w|}$.

Рассуждения, показывающие, что если из слова $w_1 = a_0^{p(|w|)} q_1 w a_0^{p(|w|)}$ с помощью
определяющих соотношений полугруппы $S$ можно получить слово $w_2 = q_a a_0^{2p(|w|)+|w|}$, то
машина $M$ принимает вход $w$, полностью аналогичны рассуждениям из леммы 2.2. из \cite{AD}.

Теперь покажем, что проблема равенства в полугруппе $S$ является {\bf PSPACE}-полной. 
То, что проблема равенства принадлежит классу {\bf PSPACE}, следует из теоремы \ref{pspace}.
Пусть теперь имеется любое множество $B$ из {\bf PSPACE}. Так как множество $C$, которое мы
моделировали, является {\bf PSPACE}-полным, то существует полиномиально вычислимая функция $f$
такая, что $x \in B \Leftrightarrow f(x) \in C$. Теперь положим
$$
g(x) = (a_0^{p(|f(x)|)} q_1 f(x) a_0^{p(|f(x)|)}, q_a a_0^{2p(|f(x)|)+|f(x)|}).
$$
С учетом всего вышедоказанного понятно, что $g$ -- полиномиально вычислимая функция, которая
сводит проблему $B$ к проблеме равенства в полугруппе $S$. То есть, $x \in B$ тогда и только
тогда, когда $g(x)$ есть пара равных слов в $S$.
\end{proof}


Автор выражает благодарность рецензенту за полезные замечания и
предложения по улучшению текста статьи.


\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).

\bibitem{AD}
S. I. Adjan, V. G. Durnev. {\it Algorithmic problems for groups and semigroups},
Uspehi Math. Nauk, {\bf 55:2} (2000), 3--94.

{\it https://www.mathnet.ru/links/dfff7cc9b43ec12ecd94fa7503d2cca1/rm267.pdf}

\bibitem{Cor}
E. W. Cardoza. {\it Computational complexity of the word problem for commutative semigroups},
MAC technical memorandum, {\bf 67} (1975), MIT.

{\it https://dspace.mit.edu/handle/1721.1/148895}

\bibitem{DM}
V. Diekert, Y. M\'etivier. {\it Partial Commutation and Traces}, 
in Rozenberg, G.; Salomaa, A. (eds.), Handbook of Formal Languages Vol. 3; Beyond Words, 
Springer-Verlag, Berlin, (1997), 457--534.

{\it https://link.springer.com/chapter/10.1007/978-3-642-59126-6\_8}

\bibitem{GJ}
M. Garey, D. Johnson. {\it Computers and Intractability: A Guide to the Theory of NP-Completeness},
W. H. Freeman and Company, (1979). 340p.

{\it https://bohr.wlu.ca/hfan/cp412/references/ChapterOne.pdf}

\bibitem{MM}
E. Mayr, A. Meyer. {\it The complexity of the word problems for commutative semigroups and polynomial ideals},
Advances in Mathematics, {\bf 46(3)} (1982), 305--329.

{\it https://core.ac.uk/download/pdf/82035833.pdf}

\bibitem{Malcev}
A. I. Malcev. {\it On homomorphisms of finite groups}, 
Uch. zapiski Ivanovskogo ped. Instituta, {\bf 18} (1958), 49--60.

\bibitem{Markov}
A. A. Markov. {\it Impossibility of some algorithms in the theory of associative systems},
Doklady AN SSSR, {\bf 55(7)} (1947), 587--590.

\bibitem{Novik}
P. S. Novikov. {\it On algorithmical undecidability of the word problem in group theory},
Trudy MIAN SSSR, {\bf 44} (1955) 3--143.

{\it https://www.mathnet.ru/links/26f6eee299f78947dcc78c29b7f9f702/tm1180.pdf}

\bibitem{Post}
E. L. Post. {\it Recursive unsolvability of a problem of Thue},
Journal of Symbolic Logic, {\bf 12:1}  (1947), 1--11.

{\it https://www.wolframscience.com/prizes/tm23/images/Post2.pdf}

\bibitem{Sav}
W. J. Savitch. {\it Relationships between nondeterministic and deterministic tape complexities},
Journal of Computer and System Sciences, {\bf 4:2} (1970), 177--192.

{\it https://www.sciencedirect.com/science/article/pii/S002200007080006X}

\end{thebibliography}


\end{document}
