\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.
}%

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

\thanks{\sc Rybalov, A.N.,
Generic polynomial algorithms for the knapsack problem in some matrix semigroups}
\thanks{\copyright \ 2022 Рыбалов А.Н.}
\thanks{\rm Работа поддержана грантом РНФ №\,22-11-20019.}
\thanks{\it Поступила 5 июля 2022 г., опубликована 1 сентября 2022 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. }
In this paper, we propose generic polynomial algorithms for 
the knapsack problems over semigroups of non-negative integer matrices of arbitrary order and
semigroup of non-negative second-order integer matrices with determinant 1.
\medskip

\noindent{\bf Keywords:} generic complexity, knapsack problems, integer matrices.
 \end{quote}
}



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

Проблема о рюкзаке является классической проблемой комбинаторной оптимизации, изучаемой многие десятилетия. 
Современное состояние исследований по этой проблеме отражено в обзорах Качиани, Иори, Локателли и Мартелло \cite{CILM1, CILM2},
а также в статье Шперлинга и Кочетова \cite{SK}. Формулировка оптимизационной проблемы о рюкзаке состоит в следующем.
Пусть имеется набор предметов, каждый из которых имеет два параметра -- объем и ценность. Также имеется рюкзак определённого объема.
Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом ограничение рюкзака на суммарный объем. Кроме того, рассматриваются еще и распознавательные варианты этой проблемы.
Например, одна из таких проблем формулируется следующим образом. Дано множество натуральных чисел $A = \{ a_1,\ldots,a_n \}$ 
и натуральное число $S$. Все числа записаны в двоичной системе счисления. 
Необходимо определить, можно ли в множестве $A$ выбрать подмножество чисел (каждое число можно повторять несколько раз), 
которые в сумме дают число $S$. Отметим, что она (при условии, когда повторы запрещены) под именем 
KNAPSACK содержится в списке NP-полных проблем в знаменитой статье Карпа \cite{Karp}.
Сейчас этот вариант распознавательной проблемы о рюкзаке называется проблемой о сумме подмножества.

Мясников, Николаев и Ушаков \cite{MNU} ввели аналог распознавательной проблемы о рюкзаке для произвольных групп (полугрупп). 
Ими была изучена вычислительная сложность этих проблем для различных
групп, в частности была доказана полиномиальная разрешимость для гиперболических групп и
доказана NP-полнота для групп Баумслага-Солитера. 
Для полугрупп целочисленных матриц эта проблема также является NP-полной,
а потому для них, при условии $\text{P} \neq \text{NP}$, нет полиномиальных алгоритмов, 
получающих решение для всех входов.

Генерические алгоритмы \cite{KMSS} решают проблемы на множестве почти всех входов, а на редких оставшихся
входах выдают неопределенный ответ.
Рыбалов \cite{Ryb1,Ryb2} построил полиномиальные генерические алгоритмы для проблемы о сумме подмножеств
в полугруппах неотрицательных целочисленных матриц произвольного порядка и 
полугруппе неотрицательных целочисленных матриц второго порядка с определителем 1. 
В данной работе предлагаются полиномиальные генерические алгоритмы для распознавательной проблемы о рюкзаке в этих полугруппах.
Также для этих полугрупп рассматриваются оптимизационные проблемы о рюкзаке, в которых необходимо
минимизировать число матричных множителей, входящих в произведение в ненулевой степени, а также
минимизировать сумму степеней матриц в произведении. Для этих проблем тоже доказывается их
полиномиальная генерическая разрешимость.

Предлагаемые алгоритмы основаны на методе динамического программирования, который состоит в следующем. 
В процессе работы алгоритма задача разбивается на подзадачи, которые подаются на вход этого же алгоритма.
Этот механизм называется {\em рекурсивным вызовом алгоритма}.
Полученные подзадачи, в свою очередь, разбиваются еще на подзадачи и так далее. В конце концов доходим до простых задач, которые
легко решаются. Всевозможных подзадач, вообще говоря, экспоненциально много. Но среди них очень много одинаковых,
а уникальных подзадач полиномиально ограниченное число. Таким образом, отслеживая появление одинаковых подзадач и
вовремя <<отсекая>> соответствующие рекурсивные вызовы, мы добиваемся того, что алгоритм работает за полиномиальное время.
Конечно же, эта схема работает не всегда: например, для всех входов какой-либо NP-полной проблемы она не работает, иначе
было бы P=NP. Однако полученные результаты показывают, что для рассматриваемых NP-полных проблем она работает для <<почти всех>> входов.


\section{Генерические алгоритмы}

Пусть $I$ -- некоторое множество входов. Для подмножества $S \subseteq I$ определим последовательность
$$
\rho_n(S) = \frac{| S_n |}{|I_n|},\ n = 1,2,3,\ldots,
$$
где $I_n$ -- множество входов размера $n$, а $S_n = S \cap I_n$ -- множество входов из $S$ размера $n$.
{\em Асимптотической плотностью} $S$ назовем предел (если он существует)
$$
\rho(S) = \lim_{n \rightarrow \infty} \rho_n(S).
$$
Множество $S$ называется {\em генерическим}, если $\rho(S) = 1$ и {\em пренебрежимым},
если $\rho(S) = 0$. 

Алгоритм $\mathcal{A}$ с множеством входов $I$ называется {\em генерическим}, если
множество $\{ x \in I : \mathcal{A}(x) \mbox{ останавливается} \}$ генерическое.
Генерический алгоритм $\mathcal{A}$ вычисляет функцию $f : I \rightarrow J$, если
$$
\forall x \in I\ \mathcal{A}(x) \mbox{ останавливается}\ \Rightarrow \ f(x) = \mathcal{A}(x).
$$
Генерический алгоритм $\mathcal{A}$ работает за полиномиальное время, если
существует полином $p(n)$ такой, что
$$
\forall x \in I\ \mathcal{A}(x) \mbox{ останавливается}\ \Rightarrow t_{\mathcal{A}}(x) < p(size(x)),
$$
где $size(x)$ -- размер входа $x$, а $t_{\mathcal{A}}(x)$ -- время работы алгоритма $\mathcal{A}$ на
входе $x$. Еще такие алгоритмы мы будем называть полиномиальными генерическими.

С практической точки зрения, когда требуется построить алгоритм, решающий конкретную алгоритмическую
проблему для почти всех входов, удобнее рассматривать алгоритмы следующего типа \cite{Hir}.
Каждый такой алгоритм останавливается на всех входах,
на входах из некоторого генерического множества выдает правильный ответ, 
а на пренебрежимом множестве остальных
входов выдает специальный ответ <<?>> -- <<Не знаю>>.

Алгоритм $\mathcal{A}$ с множеством входов $I$ и множеством 
выходов $J \cup \{ ? \}$ ($? \notin J$) называется {\em эффективно генерическим}, если
\begin{enumerate}
\item $\mathcal{A}$ останавливается на всех входах из $I$,
\item множество $\{ x \in I : \mathcal{A}(x) = ? \}$ пренебрежимо.
\end{enumerate}
Эффективно генерический алгоритм $\mathcal{A}$ вычисляет функцию $f : I \rightarrow J$, если
$$
\forall x \in I\ \mathcal{A}(x) \neq ?\ \Rightarrow \ f(x) = \mathcal{A}(x).
$$

Множество $S \subseteq I$ и соответствующая проблема распознавания $(S,I)$ {\em (эффективно) генерически разрешимы}, 
если существует (эффективно) генерический алгоритм, вычисляющий характеристическую функцию $S$.

Легко видеть, что из эффективной генерической разрешимости следует генерическая разрешимость.
Действительно, любой эффективный генерический алгоритм можно легко переделать в генерический заменив выдачу ответа 
<<?>> на бесконечное зацикливание. В обратную сторону это неверно -- см., например, теорему 2.22 и следствие 2.24 в \cite{JS}.
Однако для полиномиальной сложности верно и обратное: из полиномиальной 
генерической разрешимости следует полиномиальная эффективная разрешимость.
Действительно, если имеется полиномиальная оценка $p(n)$ на время работы генерического алгоритма
в случае, когда он останавливается, то можно завести счетчик $T$ числа шагов, и, в случае, 
если $T > p(n)$, можно обрывать вычисление и выдавать ответ <<?>>, -- в этом случае генерический алгоритм уже
не остановится. Таким образом получается эффективно генерический полиномиальный алгоритм, решающий ту же
проблему.


\section{Полугруппы целочисленных неотрицательных матриц}
 
Обозначим через $\omega$ множество натуральных чисел с нулем, а 
через $\text{M}_k(\omega)$ полугруппу матриц порядка $k$ с целыми неотрицательными элементами с обычной операцией
умножения матриц.
Порядок матриц $k$ будет фиксированным на протяжении всего подраздела.
Элементы $\text{M}_k(\omega)$ будем представлять матрицами из целых неотрицательных чисел.
Размер целого положительного числа $a$, обозначаемый $size(a)$, -- это длина его записи в двоичной системе счисления. 
Под размером матрицы $M = ||a_{ij}||$ будем понимать 
$$
size(M) = \max_{i,j=1,\ldots,k} \{ size(a_{ij}) \}.
$$
Для любого подмножества $S \subseteq \text{M}_k(\omega)$ обозначим через $S_{\leq n}$ множество всех матриц из $S$
размера $\leq n$.

Сформулируем теперь проблему о рюкзаке для полугруппы $\text{M}_k(\omega)$.
Пусть даны произвольные матрицы $(M_1, M_2, \ldots, M_n, M)$ из $\text{M}_k(\omega)$, 
каждая размером не более $n$. Определить, существуют ли
степени $\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n \in \omega$ такие, что имеет место
$$
M_1^{\varepsilon_1} M_2^{\varepsilon_2} \ldots M_n^{\varepsilon_n} = M.
$$
Размер входа $(M_1, M_2, \ldots, M_n, M)$ полагаем равным $n$.
Условимся, что если матрица $M = E$ -- единичная, то $M$ есть произведение пустого подмножества матриц,
а потому проблема суммы подмножеств с такой матрицей $M$ разрешима. Это допущение послужит для удобства
описания генерического алгоритма в дальнейшем.

Следующее утверждение говорит о том, что для этой проблемы, при условии $\text{P} \neq \text{NP}$, 
не существует полиномиального алгоритма, который решал бы ее для всех входов.

\begin{lemma} \label{np_complete}
Проблема о рюкзаке для $\text{M}_k(\omega)$ NP-полна.
\end{lemma}
\begin{proof}
Докажем, что к ней полиномиально сводится классическая проблема о рюкзаке для
натуральных чисел. Определим функцию $F : \omega \rightarrow \text{M}_k(\omega)$ следующим образом.
Для любого $a \in \omega$ положим
$$
F(a) = 
\begin{pmatrix}
1 & 0 & 0 & \ldots & 0 & a \\
0 & 1 & 0 & \ldots & 0 & 0 \\
0 & 0 & 1 & \ldots & 0 & 0 \\
\ldots \\
0 & 0 & 0 & \ldots & 1 & 0 \\
0 & 0 & 0 & \ldots & 0 & 1
\end{pmatrix},
$$
Полиномиальная сводимость сопоставляет входу $(a_1, a_2, \ldots, a_n, S)$
классической проблемы о рюкзаке для $\omega$ вход $(F(a_1), F(a_2), \ldots, F(a_n), F(S))$ 
проблемы о рюкзаке для $\text{M}_k(\omega)$.
Легко проверить, что для любого набора чисел
$\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n \in \omega$
равенство
$$
a_1 \varepsilon_1 + a_2 \varepsilon_2 + \ldots + a_n \varepsilon_n = S
$$
выполняется тогда и только тогда, когда
$$
F(a_1)^{\varepsilon_1} F(a_2)^{\varepsilon_2} \ldots F(a_n)^{\varepsilon_n} = F(S).
$$

Заметим, что ограничения на размер матриц 
$$
F(a_1), F(a_2), \ldots, F(a_n), F(S),
$$
которые фигурируют в формулировке проблемы о сумме подмножеств для матриц,
обходятся добавлением к матрицам необходимого количества единичных матриц $E_1, \ldots, E_k$.
При этом $k$ будет ограничено полиномом от $n$.
\end{proof}

Нам потребуются следующие леммы, которые были доказаны в \cite{Ryb1}.

\begin{lemma} \label{zerro}
Пусть $\mathcal{Z}$ есть множество матриц из $\text{M}_k(\omega)$ с определителем 0. 
Тогда 
$$
\lim_{n \rightarrow \infty} \frac{|\mathcal{Z}_{\leq n}|}{|\text{M}_k(\omega)_{\leq n}|} = 0.
$$
\end{lemma}

\begin{lemma} \label{split}
Пусть $S_{\leq n}$ -- множество матриц $M$ из $\text{M}_k(\omega)$ размера $\leq n$ таких, что
матричное уравнение $M = XY$ имеет более $p(n) = (2(n+1))^{k^2+1}$ различных решений $X,Y \in \text{M}_k(\omega)$
таких, что $size(X), size(Y) \leq n$.
Тогда
$$
\frac{|S_{\leq n}|}{|\text{M}_k(\omega)_{\leq n}|} < \frac{1}{2(n+1)}.
$$
\end{lemma}

Будем использовать эти утверждения для доказательства следующего результата.

\begin{theorem} \label{main1}
Проблема о рюкзаке для $\text{M}_k(\omega)$ 
является генерически разрешимой за полиномиальное время.
\end{theorem}
\begin{proof}
Опишем как работает эффективно генерический полиномиальный алгоритм $\mathcal{A}$ на входе $(M_1, \ldots, M_n, M)$ размера $n$.
\begin{enumerate}
\item Вычисляем определитель матрицы $M$. Если $det(M)=0$, выдаем ответ <<?>>. Из леммы \ref{zerro} следует,
что множество входов $(M_1, \ldots, M_n, M)$, у которых $det(M)=0$, пренебрежимо.
\item Вычисляем определители матриц $M_1, \ldots, M_n$. Выбрасывам те матрицы, у которых определитель
равен 0 -- они не могут участвовать в произведении, которое равно $M$, так как $det(M) \neq 0$.
На последующих шагах считаем, что все матрицы $M_1, \ldots, M_n, M$ невырождены.
\item В последующей работе алгоритм $\mathcal{A}$ будет осуществлять рекурсивные вызовы алгоритма $\mathcal{A}$
на других входных данных. Будем контролировать число таких вызовов, для чего заведем счетчик вызовов $R$, который в самом
начале будет равен 0.
\item Если счетчик числа рекурсивных вызовов $R$ стал равен $n p(n)$, где $p$ -- полином из леммы \ref{split}, 
то останавливаем все рекурсивные вызовы и выдаем ответ <<?>>.
\item Если $M = E$ -- единичная матрица, то останавливаем все запущенные рекурсивные вызовы алгоритма $\mathcal{A}$
и выдаем ответ <<ДА>>.
\item Для каждой матрицы $M_i$, $i=1,\ldots,n$ решаем матричное уравнение $M_i X = M$. 
Оно сводится к системе линейных уравнений, которое решаем методом Гаусса в рациональных числах.
Если решение получается в натуральных числах, то 
запускаем рекурсивно алгоритм $\mathcal{A}$ для всех входов 
$(M_{i+1},\ldots, M_n, X)$ и $(M_i,\ldots, M_n, X)$ 
таких, для которых алгоритм $\mathcal{A}$ не был запущен ранее. 
При этом каждый раз увеличиваем счетчик рекурсивных вызовов $R := R+1$. 
\item Если ни одна из этих систем неразрешима в натуральных числах, то останавливаем текущий рекурсивный вызов алгоритма
$\mathcal{A}$ и выдаем ответ <<Нет решения на данной подзадаче>>.
\item Если все запущенные рекурсивные вызовы в какой-то момент остановились и выдали ответ 
<<Нет решения на данной подзадаче>>, то выдаем ответ <<НЕТ>>.
\end{enumerate}
Докажем полиномиальность алгоритма $\mathcal{A}$. Каждая вычислительная процедура (метод Гаусса, вычисление 
определителя), используемая внутри алгоритма работает за полиномиальное время. Кроме того, число рекурсивных
вызовов алгоритма $\mathcal{A}$ самим собой ограничено полиномом -- оно не превосходит $n p(n)$,
где $p$ -- полином из леммы \ref{split}.

Докажем теперь пренебрежимость множества входов, на которых алгоритм $\mathcal{A}$ выдает ответ <<?>>. 
Из леммы \ref{split} следует, что множество входов
$(M_1, \ldots, M_n, M)$ проблемы суммы подмножеств размера $n$, в которых число решений матричного уравнения
$M = XY$ в матрицах из $\text{M}_k(\omega)$ не превосходит $p(n)$, является генерическим.
Заметим, что для любого такого входа $(M_1, \ldots, M_n, M)$ алгоритм $\mathcal{A}$ выдаст ответ, отличный от ответа <<?>>.
Для того, чтобы убедиться в этом, оценим число возможных подзадач $(M_i, \ldots, M_n, M^{\prime})$,
для которых происходят рекурсивные вызовы алгоритма $\mathcal{A}$.
Для всех матриц, кроме последней имеется не более $n$ вариантов выбора.
Для матрицы $M^{\prime}$ всегда найдется матрица $X$ такая, что $M = X M^{\prime}$. Значит число вариантов выбора
матрицы $M^{\prime}$ не может быть больше числа решений матричного уравнения
$M = XY$ в матрицах из $\text{M}_k(\omega)$, то есть, согласно лемме \ref{split}, $p(n)$. 
Итого получаем не более $n p(n)$ вариантов
для возможных подзадач $(M_i, \ldots, M_n, M^{\prime})$. А так как в алгоритме счетчик числа рекурсивных вызовов
ограничен как раз значением $n p(n)$, то все эти рекурсивные вызовы происходят и соответствующие подзадачи решаются.
Поэтому на таких входах алгоритм обязательно выдает ответ, отличный от <<?>>.
\end{proof}

Отметим, что описанный алгоритм можно несколько ускорить, используя процедуру вычисления определителя,
близкую по сложности к умножению матриц \cite{NP}. Для умножения матриц можно использовать алгоритм
Штрассена-Винограда \cite{St,Win}, который эффективнее обычного алгоритма умножения матриц порядка
большего нескольких сотен. Обзоры современных алгоритмов быстрого матричного умножения есть в \cite{KS, Ros}.
Также для проверки невырожденности целочисленных матриц можно использовать алгоритмы приведения к нормальной
форме Смита \cite{BLS}.

Сформулируем теперь две оптимизационные проблемы о рюкзаке для полугруппы $\text{M}_k(\omega)$.
Пусть даны произвольные матрицы $(M_1, M_2, \ldots, M_n, M)$ из $\text{M}_k(\omega)$, 
каждая размером не более $n$. Найти степени $\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n \in \omega$ 
такие, что
$$
M_1^{\varepsilon_1} M_2^{\varepsilon_2} \ldots M_n^{\varepsilon_n} = M
$$
и такие, что
\begin{enumerate}
\item число ненулевых чисел среди $\varepsilon_1, \ldots, \varepsilon_n$ минимально 
({\it проблема минимизации числа множителей рюкзака}),
\item сумма $\varepsilon_1 + \ldots + \varepsilon_n$ минимальна ({\it проблема минимизации суммы степеней множителей рюкзака}).
\end{enumerate}

\begin{theorem} \label{opt1}
Проблемы минимизации числа и суммы степеней множителей рюкзака 
для $\text{M}_k(\omega)$ являются генерически разрешимыми за полиномиальное время.
\end{theorem}
\begin{proof}
Рассмотрим алгоритм из доказательства теоремы \ref{main1}. Если в каждой подзадаче,
помимо матриц хранить еще текущие показатели степеней матриц, которые могут входить
в будущие решения, то в результате его работы находятся показатели $\varepsilon_1, \ldots, \varepsilon_n$ для
всех возможных решений матричного уравнения
$$
M_1^{\varepsilon_1} M_2^{\varepsilon_2} \ldots M_n^{\varepsilon_n} = M.
$$
При этом на шаге 5 нужно, выяснив, что решение есть, не обрывать вычисления, а добавить 
найденное решение в список решений и оборвать только текущий рекурсивный вызов.
В итоге, учитывая, что число этих решений ограничено полиномом от размера входа, можно за полиномиальное
время найти то, которое минимизирует нужный нам параметр.
\end{proof}


\section{Полугруппа целочисленных неотрицательных матриц второго порядка с определителем 1}

Через $SL_2(\omega)$ обозначим полугруппу матриц второго порядка 
с целыми неотрицательными целыми элементами, определитель которых равен 1, 
с обычной операцией умножения матриц. Элементы $SL_2(\omega)$ будем представлять матрицами, а под размером матрицы 
$$
M =
\begin{pmatrix}
a & b \\
c & d
\end{pmatrix}
$$
будем понимать максимум из размеров натуральных чисел $a,b,c,d$, записанных в двоичной системе счисления.
Проблема о рюкзаке и проблемы минимизации числа и суммы степеней множителей рюкзака для $SL_2(\omega)$
формулируются аналогично тому, как это делалось в предыдущем разделе.
Согласно лемме \ref{np_complete}, проблема о рюкзаке для $SL_2(\omega)$ является NP-полной.
Для любого подмножества $S \subseteq SL_2(\omega)$ обозначим через $S_{\leq n}$ множество всех матриц из $S$
размера $\leq n$.

Нильсен в \cite{Nielsen} доказал, что полугруппа $SL_2(\omega)$ является свободной полугруппой с двумя порождающими
$$
A = \begin{pmatrix}
1 & 1 \\
0 & 1
\end{pmatrix},\
B = \begin{pmatrix}
1 & 0 \\
1 & 1
\end{pmatrix}.
$$
Таким образом, любая матрица из $SL_2(\omega)$ единственным образом представляется в виде 
произведения матриц, каждая из которых есть либо $A$, либо $B$. 
Будем называть такое произведение {\em нормальной формой} элемента из $SL_2(\omega)$.

Опишем алгоритм $\Psi$ приведения матриц из $SL_2(\omega)$ к нормальной форме. Этот алгоритм работает на матрице 
$$
M =
\begin{pmatrix}
a & b \\
c & d
\end{pmatrix} = M_0 =
\begin{pmatrix}
a_0 & b_0 \\
c_0 & d_0
\end{pmatrix}
$$
размера $n$ следующим образом.
\begin{enumerate}
\item Вначале инициализируем счетчик числа раундов $k=0$.
\item Вначале выходная строка $w_0$ пустая.
\item Если $M_k = E$, выдаем ответ $w_k$. Через $M_k$ обозначается матрица, а через $w_k$ выходная строка на текущем раунде $k$.
\item Если число раундов $k = n^5$, то выдаем ответ <<?>>. Такая оценка необходима для получения нужной верхней границы на долю
тех входов, для которых алгоритм не может найти нормальную форму (более подробные разъяснения см. в \cite{Ryb2}).
\item Пусть матрица 
$
M_k =
\begin{pmatrix}
a_k & b_k \\
c_k & d_k
\end{pmatrix}
$ 
на данном раунде. Если $a_k \leq c_k$, то полагаем
$$
M_{k+1} = B^{-1} M_k =
\begin{pmatrix}
a_k & b_k \\
c_k - a_k & d_k - b_k
\end{pmatrix}
$$
и $w_{k+1} = B w_k$. Иначе (если $a_k > c_k$), полагаем
$$
M_{k+1} = A^{-1} M_k =
\begin{pmatrix}
a_k - c_k & b_k - d_k \\
c_k & d_k
\end{pmatrix}
$$
и $w_{k+1} = A w_k$.
\item Увеличиваем счетчик числа раундов $k := k+1$.
\item Возвращаемся на шаг 3.
\end{enumerate}

Следующая лемма была доказана в \cite{Ryb2}.

\begin{lemma} \label{bound_psi}
Алгоритм $\Psi$ является полиномиальным и эффективно генерическим. 
Более того, пусть $S = \{ M \in SL_2(\omega) : \Psi(M) = ? \}$. 
Тогда существует константа $C > 0$ такая, что для любого $n$ выполнено
$$
\frac{|S_{\leq n}|}{|SL_2(\omega)_{\leq n}|} < \frac{C}{n^2}.
$$
\end{lemma}

Будем использовать это утверждение для доказательства следующего результата.

\begin{theorem} \label{main2}
Проблема о рюкзаке в полугруппе $SL_2(\omega)$ генерически полиномиально разрешима.
\end{theorem}
\begin{proof}
Рассмотрим эффективно генерический полиномиальный алгоритм $\Sigma$,
который будет работать на входе $(M_1, \ldots, M_n, M)$ в два этапа. 

Сначала с помощью алгоритма $\Psi$ все матрицы $M_1, \ldots, M_n, M$ приводятся к нормальной форме в виде слов
$(w_1, \ldots, w_n, w)$ над алфавитом $\{ A,B \}$ как элементы свободной полугруппы. Если при этом алгоритм $\Psi$
хотя бы раз выдал ответ <<?>>, то и алгоритм $\Sigma$ выдает ответ <<?>>. Иначе слова $(w_1, \ldots, w_n, w)$ 
передаются на второй этап. Заметим, что множество входов $G$, на котором алгоритм $\Sigma$ не выдает ответ <<?>>, 
является генерическим. Действительно
$$
G_n = \{ (M_1, \ldots, M_n, M) : \Psi(M_1) \neq ?, \ldots, \Psi(M_n) \neq ?, \Psi(M) \neq ? \}.
$$
Откуда по лемме \ref{bound_psi}
$$
\rho_n(G) > \left( 1- \frac{C}{n^2} \right)^n \left( 1- \frac{C}{n^2} \right) =
\left( \left( 1- \frac{C}{n^2} \right)^{n^2} \right)^{1/n} \left( 1- \frac{C}{n^2} \right)
$$
и значит $\lim_{n \rightarrow \infty} \rho_n(G) = 1$.

На втором этапе решается проблема о рюкзаке в свободной полугруппе $\{ A,B \}^{\ast}$. 
Имеются слова  $(w_1, \ldots, w_n, w)$ над алфавитом $\{ A,B \}$, причем их длины ограничены $n^5$ -- 
это следует из описания алгоритма $\Psi$. Нужно выяснить, существуют 
ли степени $\varepsilon_1, \ldots, \varepsilon_n \in \omega$ такие, что $w_1^{\varepsilon_1} \ldots w_n^{\varepsilon_n} = w$. 
Для этого применим следующий алгоритм $\Omega$. Для удобства описания алгоритма будем 
считать, что при пустом слове $w$ проблема разрешима (ответ ДА).
\begin{enumerate}
\item Если слово $w$ пустое, останавливается (и останавливает все запущенные рекурсивные вызовы) 
и выдает ответ <<ДА>>.
\item Среди слов $w_1, \ldots, w_n$ ищет все слова $w_{j_1}, \ldots, w_{j_k}$, которые являются 
префиксами слова $w$.  Если таких слов нет, то останавливает текущий рекурсивный вызов и выдает 
ответ <<Нет решения на данной подзадаче>>.
\item Запускает рекурсивно алгоритм $\Omega$ для всех входов 
$$
(w_{j_m + 1}, w_{j_m + 2}, \ldots, w_n, \overline{w}_{j_m} w),
$$ 
и
$$
(w_{j_m}, w_{j_m + 1}, \ldots, w_n, \overline{w}_{j_m} w),
$$ 
таких, для которых алгоритм $\Omega$ не был запущен ранее. 
Здесь через $\overline{w}_{j_m} w$ обозначено слово $w$ без начального куска $w_{j_m}$.
\item Если все запущенные рекурсивные вызовы в какой-то момент остановились и выдали ответ 
<<Нет решения на данной подзадаче>>, выдает ответ <<НЕТ>>.
\end{enumerate}
Для того, чтобы доказать полиномиальность алгоритма $\Omega$, заметим, что число возможных рекурсивных вызовов
$\Omega$ не превосходит числа возможных подзадач вида $(w_m, w_{m+1}, \ldots, w_n, w^{\prime})$,  
где $w^{\prime}$ -- слово $w$ без некоторого начального куска. Число таких подзадач не превосходит 
$n \cdot |w| < n \cdot n^5 = n^6$ -- ограничено полиномом от $n$. 
\end{proof}

Доказательство следующей теоремы аналогично доказательству теоремы \ref{opt1}.

\begin{theorem}
Проблемы минимизации числа и суммы степеней множителей рюкзака 
для $SL_2(\omega)$ являются генерически разрешимыми за полиномиальное время.
\end{theorem}

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


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

\bibitem{BLS}
S. Birmpilis, G. Labahn, A. Storjohann. {\it A fast algorithm for computing
the Smith normal form with multipliers for a nonsingular integer matrix},
Journal of Symbolic Computation, {\bf 116} (2023), 146--182. 
{\it https://doi.org/10.1016/j.jsc.2022.09.002}

\bibitem{CILM1}
V. Cacchiani, M. Iori, A. Locatelli, S. Martello. {\it Knapsack problems – An
overview of recent advances. Part I: Single knapsack problems}, 
Computers and Operations Research, {\bf 143:105692} (2022), 1--13. 
{\it https://doi.org/10.1016/j.cor.2021.105692}

\bibitem{CILM2}
V. Cacchiani, M. Iori, A. Locatelli, S. Martello. {\it Knapsack problems –
An overview of recent advances. Part II: Multiple, multidimensional,
and quadratic knapsack problems}, Computers and Operations Research,
{\bf 143:105693} (2022), 1--14. 
{\it https://doi.org/10.1016/j.cor.2021.105693}

\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{Hir}
D. Hirschfeldt. {\it Some Questions in Computable Mathematics}, 
Computability and Complexity, (2017), 22--55.
{\it https://math.uchicago.edu/~drh/Papers/Papers/open.pdf}

\bibitem{JS} 
C. Jockusch, P. Schupp. 
{\it Generic computability, Turing degrees, and asymptotic density},
Journal of the London Mathematical Society, {\bf 85:2} (2012), 472--490.
{\it https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.225.1953\&rep=rep1\&type=pdf}


\bibitem{KMSS} 
I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain.
{\it Generic-case complexity and decision problems in group theory},
Journal of Algebra, {\bf 264} (2003), 665--694.
{\it https://arxiv.org/pdf/math/0203239}

\bibitem{Karp} 
R. Karp. {\it Reducibility among combinatorial problems},
Complexity of Computer Computations. The IBM Research Symposia Series, (1972), 85--103.
{\it https://link.springer.com/chapter/10.1007/978-1-4684-2001-2\_9}

\bibitem{KS}
E. Karstadt, O. Schwartz. {\it Matrix multiplication, a little faster}, Journal of ACM,
{\bf 67:1} (2020), article no. 1, 1--31. 
{\it https://doi.org/10.1145/3364504}

\bibitem{MNU}
A. Miasnikov, A. Nikolaev, A. Ushakov. {\it Knapsack problems in groups}, 
Mathematics of Computation, {\bf 84} (2015), 987--1016.
{\it https://arxiv.org/pdf/1302.5671}

\bibitem{NP}
V. Neiger, C. Pernet. {\it Deterministic computation of the characteristic
polynomial in the time of matrix multiplication}, Journal of Complexity,
{\bf 67:101572} (2021), 1--35. 
{\it https://doi.org/10.1016/j.jco.2021.101572}

\bibitem{Nielsen}
J. Nielsen. {\it Die Gruppe der dreidimensionalen Gittertransformationen},
Kgl. Danske Vid. Selsk., Math.-fys. Medd., {\bf 5:12} (1924), 3--29. (in German)
{\it http://gymarkiv.sdu.dk/MFM/kdvs/mfm\%201-9/mfm-5-12.pdf}

\bibitem{Ros}
A. Rosowski. {\it Fast commutative matrix algorithms}, Journal of Symbolic
Computation, {\bf 114} (2023), 302--321. 
{\it https://doi.org/10.1016/j.jsc.2022.05.002}

\bibitem{Ryb1}
A. Rybalov. {\it On generic complexity of the subset sum problem for semigroups of integer matrices},
Applied Discrete Mathematics, {\bf 50} (2020), 118--126. (in Russian)
{\it http://www.mathnet.ru/php/archive.phtml?wshow=paper \& jrnid=pdm \& paperid=727 \& option\_lang=rus}

\bibitem{Ryb2}
A. Rybalov. {\it On generic complexity of the subset sum problem in monoids and groups of integer matrix of order two},
Herald of Omsk State University, {\bf 25:4} (2020), 10--15. (in Russian)
{\it https://elib.omsu.ru/issues/183/7188.pdf}

\bibitem{SK}
S.M. Shperling, Y.A. Kochetov. {\it A knapsack problem for rectangles
under center-of-gravity constraints}, Journal of Applied and Industrial
Mathematics. {\bf 16:3} (2022), 563--571. 
{\it https://doi.org/10.1134/S199047892203019X}

\bibitem{St}
V. Strassen. {\it Gaussian elimination is not optimal}, Numerische
Mathematik, {\bf 13:4} (1969), 354--356. 
{\it https://doi.org/10.1007/BF02165411}

\bibitem{Win}
S. Winograd. {\it On multiplication of 2x2 matrices}, Linear Algebra
and its Applications, {\bf4:4} (1971), 381--388. 
{\it https://doi.org/10.1016/0024-3795(71)90009-7}

\end{thebibliography}


\end{document}
