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

\def\udcs{510.67,~519.151} %Здесь автор определяет УДК своей работы
\def\mscs{03C48,~05B35} %Здесь автор определяет классификаторы 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 Том 16, стр. 144--144 (2019) \hspace{65mm}{\rm\small УДК \udcs}}
     \newline
     	{\rm\small DOI~10.33048/semi.2019.16.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

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


\thispagestyle{empty}

\title[Исследование систем уравнений над конечными матроидами]{Исследование систем уравнений над различными классами конечных матроидов}
\author{{А.В. ИЛЬЕВ}}%
\address{Artyom Victorovich Ilev  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} Pevtsova str., 13,
\newline\hphantom{iii} 644043, Omsk, Russia}%
\email{artyom\_iljev@mail.ru}%

\thanks{\sc Ilev, A.V.,
Study of systems of equations over various classes of finite matroids}
\thanks{\copyright \ 2022 Ильев А.В.}
\thanks{\rm Работа выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022-0003.}
\thanks{\it Поступила 1 января 2015 г., опубликована 31 декабря 2015 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. } In the paper, it is proved that the problem of checking compatibility of a finite system of equations over a matroid of rank not exeeding $k$ is $\mathcal{NP}$-complete for ${k \geqslant 2}$.
Moreover, it is proved that the problem of checking compatibility of a finite system of equations over a 
\linebreak
$k$-uniform matroid is also $\mathcal{NP}$-complete for ${k \geqslant 2}$, and the problem of checking compatibility of a finite system of equations over a partition matroid of rank not exeeding $k$ is polynomially solvable for ${k=2}$ and 
\linebreak
$\mathcal{NP}$-complete for ${k \geqslant 3}$.\medskip

\noindent{\bf Keywords:} graph, matroid, system of equations, computational complexity.
 \end{quote}
}


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

Решение систем уравнений над вещественными, комплексными, рациональными и целыми числами является традиционным направлением исследований в алгебраической геометрии, которому посвящены многочисленные теоретические и практические исследования.
Алгоритмические проблемы, связанные с решением систем уравнений, чаще всего оказываются либо неразрешимыми, либо разрешимыми, но вычислительно трудными.
Из наиболее известных неразрешимых проблем можно выделить проблему решения полиномиальных уравнений над кольцом целых чисел~\cite{m1970}.
К числу разрешимых проблем, имеющих экспоненциальную сложность, относится проблема решения систем полиномиальных уравнений над полями комплексных и вещественных чисел~\cite{mm1982} и проблема решения систем полиномиальных уравнений над конечными полями, которая эквивалентна $\mathcal{NP}$-полной проблеме выполнимости булевых формул~\cite{c1971}.

В последние годы в алгебраической геометрии активно изучаются системы уравнений над произвольными алгебраическими системами, где уравнениями являются атомарные формулы языка алгебраической системы~\cite{dmr2016}.
И в рамках этого направления исследований также естественным образом возникают вопросы разрешимости и вычислительной сложности алгоритмических проблем.
Например, было доказано, что проблема совместности систем уравнений над конечными частично упорядоченными множествами является $\mathcal{NP}$-полной в том случае, когда проверяется существование решения, состоящего из попарно различных элементов частично упорядоченного множества~\cite{nr2018}, или что экзистенциальная теория класса всех конечных полей является $\mathcal{NP}$-трудной, а универсальная теория этого класса является co-$\mathcal{NP}$-трудной~\cite{r2019}.

Кроме того, ряд результатов был получен и для обыкновенных графов и матроидов.
Вопросы разрешимости универсальных теорий различных классов графов, которые имеют тесную связь с решением систем уравнений над конечными графами, подробно рассматривались в~\cite{i2016n1}.
Затем предлагался алгоритм решения системы уравнений над произвольным конечным графом, который находил её общее решение~--- координатный граф~\cite{ir2017}.
В дальнейшем была подсчитана вычислительная сложность этого алгоритма и доказывалось, что задача проверки совместности конечной системы уравнений над обыкновенным графом является $\mathcal{NP}$-полной~\cite{ii2021}.
Для различных классов матроидов вопросы аксиоматизируемости и разрешимости их универсальных теорий были рассмотрены в \cite{i2016n2, ii2019, ii2020}.

В настоящей работе исследуются конечные системы уравнений над графами и матроидами.
Доказано, что распознавательный вариант задачи о $p$-рас\-краске графа полиномиально сводится к задаче проверки совместности системы уравнений над конечным полным $p$-дольным графом, откуда следует её 
\linebreak
$\mathcal{NP}$-полнота при ${p\geqslant 3}$.
В свою очередь, эта задача полиномиально сводится к частному случаю задачи проверки совместности системы уравнений над конечным матроидом ранга, не превосходящего~$k$, которая, таким образом, тоже является $\mathcal{NP}$-полной задачей при ${k \geqslant 2}$.
Помимо этого, показано, что задача проверки совместности системы уравнений над конечным $k$-однородным матроидом также $\mathcal{NP}$-полна при ${k \geqslant 2}$, а задача проверки совместности системы уравнений над конечным матроидом разбиения ранга, не превосходящего~$k$, полиномиально разрешима при ${k = 2}$ и $\mathcal{NP}$-полна при ${k \geqslant 3}$.


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

Поскольку в данной работе рассматриваются только алгебраические системы, языки которых не содержат функциональных символов, то здесь и далее все определения адаптированы под предикатный случай.

Множество $T_{\rm L}(X)$ {\it термов} языка~${\rm L}$ от переменных из множества~$X$ состоит из всех переменных $x \in X$ и всех констант~$c \in {\rm C}$ языка~${\rm L}$.
Множество $At_{\rm L}(X)$ {\it атомарных формул} языка~${\rm L}$ от переменных из множества~$X$ состоит из всех формул вида ${t_i=t_j}$ и $R(t_1,t_2,...,t_k)$, где $t_1,t_2,...,t_k \in T_{\rm L}(X)$, а 
$R(x_1,x_2,...,x_k)$~--- предикат языка~${\rm L}$.
Атомарные формулы называются {\it уравнениями}, а произвольные подмножества $S \subseteq At_{\rm L}(X)$~--- {\it системами уравнений} языка~${\rm L}$.

Для обыкновенных графов и матроидов мы сначала вспомним их традиционные определения, а затем зададим эти объекты как бесконечные алгебраические системы.

{\it Граф}~--- это пара $G = (V, E)$, где $V$~--- непустое множество элементов, называемых {\it вершинами}, a $E$~--- множество неупорядоченных пар различных элементов из $V$, называемых {\it рёбрами}.
Если $(u, v) \in E$, то вершины $u$ и $v$ называются {\it смежными}.

{\it Граф}~--- это алгебраическая система $G = \langle V, {\rm L}_E\rangle$, носитель которой $V$~--- непустое не более чем счётное множество, а язык ${\rm L}_E = \langle E, =\rangle$ состоит из бинарного предиката смежности вершин и предиката равенства, причём предикат смежности является {\it иррефлексивным и симметричным}, т.\,е. удовлетворяет условиям:

1) $\forall x\ \neg E(x, x)$ (иррефлексивность);

2) $\forall x \forall y\ (E(x, y) \rightarrow E(y, x))$ (симметричность).

Понятие матроида впервые было введено в~\cite{w1935} и охватывало только конечный случай.

{\it Матроид}~--- это пара $M=(U,{\mathcal I})$, где $U$~--- непустое конечное множество, $\mathcal{I}$~--- непустое семейство его подмножеств (называемых {\it независимыми}), обладающее свойствами:

(I1) если $I \in \mathcal{I}, \ J \subseteq I$, то $J \in \mathcal{I}$ (наследственность);

(I2) для любых $I, J \in \mathcal{I}$ таких, что $|J|=|I|+1$, существует элемент $j \in J \setminus I$, для которого $I \cup \{j\} \in \mathcal{I}$ (пополнение).

Максимальные независимые подмножества множества $A \subseteq U$ называются {\it базами} множества~$A$.
Максимальные независимые подмножества множества $U$ называются {\it базами матроида $M$}. Напомним, что в матроиде все базы любого множества равномощны.
{\it Рангом} $r(A)$ множества $A$ называется мощность любой базы $A$.
Число $r(M) = r(U)$ называется {\it рангом матроида $M$}.

В литературе наряду с конечными рассматриваются также бесконечные матроиды.
Пусть $k \in \mathbb{N}$~--- фиксированное число.
В общем случае {\it матроид ранга, не превосходящего~$k$},~--- это пара $M=(U,{\mathcal I})$, где $U$~--- непустое (возможно, бесконечное) множество, $\mathcal{I}$~--- непустое семейство его независимых подмножеств, обладающее свойствами наследственности, пополнения, а также свойством (I3):

(I3) $|I|\leqslant k$ для всех $I \in {\mathcal I}$.

Чтобы определить класс {\it матроидов фиксированного ранга $k \in \mathbb{N}$}, в приведённом 
выше определении условие (I3) нужно заменить на условие~(I3$'$):

(I3$'$) $r(M)=k$.

{\it Матроид ранга, не превосходящего~$k$,}~--- это алгебраическая система 
\linebreak
${M = \langle U, {\rm L}_{I_k}\rangle}$, где $U$~--- непустое не более чем счётное множество, а язык 
\linebreak
${{\rm L}_{I_k} = \langle I_0, I_1,..., I_k, =\rangle}$ состоит из $k+1$ предиката независимости, местность каждого из которых совпадает с его порядковым номером, и предиката равенства, причём предикаты независимости удовлетворяют условиям {\it неупорядоченности} и {\it неповторения элементов}, {\it наследственности} и {\it пополнения}:

$\bullet\ \forall x_1\ ...\ \forall x_n\ [I_n(x_1,...,x_n) \rightarrow 
\bigwedge\limits_{\pi} I_n(\pi(x_1),...,\pi(x_n))]$, 
где $\pi$ пробегает по всем перестановкам элементов $x_1, ..., x_n$, $\ n\in\{1,...,k\}$;

$\bullet\ \forall x_1\ ...\ \forall x_n\ [I_n(x_1,...,x_n) \rightarrow 
\bigwedge\limits_{i \not = j} (x_i \not = x_j)]$, $\ n\in\{1,...,k\}$;

$\bullet\ \forall x_1\ ...\ \forall x_n\ [(I_n(x_1,...,x_n) \rightarrow 
I_{n-1}(x_2,...,x_n) \wedge\ I_{n-1}(x_1,x_3,...,x_n) \wedge\ ...\ \wedge I_{n-1}(x_1,...,x_{n-1}))\ \wedge~I_0]$, $\ n\in\{2,...,k\}$;

$\bullet\ \forall x_1\ ...\ \forall x_n\ \ \forall y_1\ ...\ \forall y_{n+1}\ \ [\!\ I_n(x_1,...,x_n)\ \wedge\ 
I_{n+1}(y_1,...,y_{n+1})\ \rightarrow 
\linebreak 
\bigvee\limits_{i \in \{1,...,n+1\}} I_{n+1}(x_1,...,x_n,y_i)\ ]$, $\ n\in\{1,...,k-1\}$.

Чтобы определить {\it матроид фиксированного ранга $k$}, в приведённое выше определение нужно добавить ещё одну аксиому:

$\bullet\ \exists x_1\ ...\ \exists x_k\ I_k(x_1,...,x_k)$.

В дальнейшем в работе будут использоваться следующие обозначения систем уравнений.

$S_G$~--- система уравнений языка ${\rm L}_E$ над графом~$G$.
Каждая такая система состоит из уравнений вида $E(x_i,x_j)$, $E(x_i,v_j)$, $E(v_i,v_j)$, $x_i=x_j$, $x_i=v_j$, $v_i=v_j$.

$S_{M,k}$~--- система уравнений языка ${\rm L}_{I_k}$ над матроидом~$M$.
Каждая такая система состоит из уравнений вида $I_0$, $I_1(x_i)$, $I_1(u_j)$, $I_2(x_i,x_j)$, $I_2(x_i,u_j)$, 
\linebreak
$I_2(u_i,u_j)$, ..., $I_k(x_{i_1},x_{i_2},...,x_{i_k})$, $I_k(x_{i_1},...,x_{i_{k-1}},u_{j_1})$, ..., $I_k(x_{i_1},u_{j_1},...,u_{j_{k-1}})$, 
\linebreak
$I_k(u_{j_1},u_{j_2},...,u_{j_k})$, $x_i=x_j$, $x_i=u_j$, $u_i=u_j$.

Отметим, что при $k_1<k_2$ для любой системы уравнений $S_{M,k_1}$ существует система уравнений $S_{M,k_2}$ такая, что $S_{M,k_1}$ совпадает с $S_{M,k_2}$.

Мы будем рассматривать только конечные системы уравнений {\it диофантовых языков}, т.\,е. таких языков, в~которых множество констант совпадает с~множеством элементов алгебраической системы.


%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\section{Совместность систем уравнений над полными многодольными графами}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Граф~$G$ называется {\it $p$-дольным}, если множество его вершин можно разбить на $p$~непересекающихся подмножеств~--- долей так, что каждое ребро в~$G$ соединяет какую-нибудь вершину одной доли с какой-либо вершиной другой доли.
Граф~$G$ называется {\it полным $p$-дольным}, если он является $p$-дольным графом и любые его две вершины из разных долей смежны.

Мы будем называть {\it графом системы уравнений $S_G$}, состоящей из уравнений вида $E(x_i,x_j)$, граф $H = (V_X,E_X)$, в котором множество вершин $V_X$ взаимно однозначно соответствует множеству переменных~$X$, а множество рёбер~$E_X$ определяется уравнениями системы $S_G$.

%Лемма 1
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{lemma}
\label{lem1}
Система $S_G$, состоящая из уравнений вида $E(x_i,x_j)$, совместна над полным $p$-дольным графом~$G$ тогда и только тогда, когда $p\geqslant q$, где $q$~--- минимальное количество долей, на которые можно распределить вершины графа системы~$S_G$.
\end{lemma}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

\begin{proof}
1) Необходимость. Как и в случае произвольного графа~$G$, переменные $\{x_i\}$ системы уравнений $S_G$, принимающие попарно различные значения на графе~$G$, и уравнения $E(x_i,x_j)$ образуют граф, изоморфный ка\-кому-то подграфу графа~$G$.
При этом переменные $\{x_j\}$, принимающие одинаковые значения на графе~$G$, попадают в одну долю графа системы $S_G$. Следовательно, $p\geqslant q$.

2) Достаточность. Положим, что переменные $\{x_i\}$, попавшие в одну долю графа системы уравнений $S_G$, принимают одинаковые значения на графе~$G$.
Тогда достаточным условием совместности системы $S_G$ над графом~$G$ будет наличие в нём клики размера~$q$. Так как $G$~--- полный $p$-дольный граф, то такая клика очевидным образом существует при $p\geqslant q$.
\end{proof}

Минимальное количество долей, на которые можно распределить вершины произвольного графа, равно минимальному числу цветов, в которое можно раскрасить вершины графа так, чтобы любые две его смежные вершины имели разные цвета.
Данная раскраска вершин графа называется {\it правильной}.
Т.\,е. при определении совместности системы уравнений над полным $p$-дольным графом~$G$ естественным образом возникает задача о минимальной правильной раскраске графа.
Поэтому лемму~\ref{lem1} можно переформулировать следующим образом.

%Лемма 2
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{lemma}
\label{lem2}
Система $S_G$, состоящая из уравнений вида $E(x_i,x_j)$, совместна над полным $p$-дольным графом~$G$ тогда и только тогда, когда граф системы~$S_G$ может быть правильно раскрашен не более, чем в $p$~различных цветов.
\end{lemma}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

%Теорема 1
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{theorem}
\label{th1}
Задача проверки совместности произвольной системы уравнений~$S_G$ над конечным полным $p$-дольным графом~$G$ является $\mathcal{NP}$-полной задачей при $p\geqslant 3$.
\end{theorem}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

\begin{proof}
Для доказательства теоремы достаточно показать, что к задаче проверки совместности системы уравнений~$S_G$ над конечным полным 
\linebreak
$p$-дольным графом~$G$ полиномиально сводится какая-нибудь другая $\mathcal{NP}$-полная задача распознавания~\cite{gj1982}, например, распознавательный вариант задачи о 
\linebreak
$p$-раскраске графа при $p\geqslant 3$.

{\bf Задача о \textit{p}-раскраске графа.}
Дан $n$-вершинный граф $H = (V,E)$ и натуральное число ${p \leqslant n}$.
Можно ли правильно раскрасить граф~$H$ в $p$~различных цветов?

По лемме \ref{lem2} для ответа на вопрос задачи о \textit{p}-раскраске графа~$H$ нужно определить, совместна ли над произвольным полным $p$-дольным графом~$G$, например кликой~$K_p$, система уравнений вида ${S_G = \big\{E(x_i,x_j)\big\}}$ такая, что граф системы~$S_G$ изоморфен графу~$H$.

Таким образом, задача проверки совместности системы уравнений~$S_G$ над конечным полным $p$-дольным графом~$G$ является $\mathcal{NP}$-полной.
\end{proof}

Отметим, что задача проверки совместности произвольной системы уравнений~$S_G$ над конечным полным двудольным графом~$G$ является полиномиально разрешимой~\cite{ii2021}.


%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\section{Совместность систем уравнений над матроидами ранга, не превосходящего~\textit{k}}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Прежде всего рассмотрим класс матроидов ранга~2.
Для него существует девять видов уравнений из множества систем уравнений $\{S_{M,2}\}$: $I_0$, $I_1(x_i)$, $I_1(u_j)$, $I_2(x_i,x_j)$, $I_2(x_i,u_j)$, $I_2(u_i,u_j)$, $x_i=x_j$, $x_i=u_j$, $u_i=u_j$.

Произвольному матроиду ранга~$2$ можно поставить в соответствие граф, рёбра которого соответствуют $2$-элементным базам матроида, а изолированные вершины~--- $1$-элементным зависимым множествам матроида.
Рассмотрим матроид $M$ ранга~$2$, все $1$-элементные множества которого независимы и которому соответствует граф $G$ без изолированных вершин.

%Предложение 1
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{proposition}
\label{pr1}
В графе~$G$ любая вершина смежна хотя бы с одним концом любого ребра.
\end{proposition}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

\begin{proof}
Справедливость этого утверждения следует непосредственно из аксиомы пополнения матроида.
\end{proof}

%Лемма 3
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{lemma}
\label{lem3}
Существует взаимно однозначное соответствие между классом матроидов ранга~$2$, все $1$-элементные множества которых независимы, и классом полных $p$-дольных графов.
\end{lemma}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

\begin{proof}
1) Докажем, что граф~$G$, соответствующий матроиду~$M$ ранга~$2$, все $1$-элементные множества которого независимы, является полным 
\linebreak
$p$-дольным графом.

В силу предложения~\ref{pr1} любой граф, соответствующий матроиду~$M$, является связным.
Поэтому вершины этого графа можно распределить на некоторое наименьшее количество долей, каждая из которых будет соединена с другими долями хотя бы одним ребром~--- иначе эту долю необходимо было бы объединить с какой-то другой.

Рассмотрим две произвольные доли графа~$G$ и соединяющее их ребро.
Будем считать, что обе доли имеют не меньше двух попарно различных вершин графа.
Обозначим их $u_1, u_2$ и $v_1, v_2$ соответственно, а существующее ребро~--- $(u_1,v_1)$.

Тогда по предложению~\ref{pr1} вершины $u_2$~и~$v_2$ должны быть смежны хотя бы с одним концом ребра $(u_1,v_1)$, следовательно, существуют рёбра $(u_2,v_1)$ и $(u_1,v_2)$.
Но тогда вершина~$u_2$ должна быть смежна хотя бы с одним концом ребра $(u_1,v_2)$, а вершина~$v_2$~--- хотя бы с одним концом ребра $(u_2,v_1)$.
Значит, существует также ребро $(u_2,v_2)$ (см. рис.\,1).

\begin{figure}[h]
%
\begin{picture}(0,0)(87,83)
\put(45,00){\line(0,1){80}}
\put(125,00){\line(0,1){80}}
\put(45,0){\line(1,1){80}}
\put(45,80){\line(1,-1){80}}
%
\put(45,0){\circle*{3}}
\put(125,0){\circle*{3}}
\put(45,80){\circle*{3}}
\put(125,80){\circle*{3}}
\end{picture}
%
\put(-55,-2){$u_1$}
\put(42,-2){$u_2$}
\put(-54,-88){$v_1$}
\put(42,-88){$v_2$}
%
\begin{center}
Рис.\,1.
\end{center}
\end{figure}

Существование необходимых рёбер в случае, когда одна из рассматриваемых долей графа~$G$ содержит ровно одну вершину, доказывается аналогично.
Таким образом, каждая вершина любой из долей графа~$G$ смежна с каждой вершиной любой другой его доли, т.\,е. граф~$G$ является полным $p$-дольным графом.

2) Доказательство того, что полному $p$-дольному графу~$G$ соответствует матроид~$M$ ранга~$2$, все $1$-элементные множества которого независимы, следует непосредственно из предложения~\ref{pr1}.
Фактически, это утверждение является иной формулировкой аксиомы пополнения~(I2).
\end{proof}

%Теорема 2
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{theorem}
\label{th2}
Задача проверки совместности произвольной системы уравнений~$S_{M,2}$ над конечным матроидом~$M$ ранга~$2$ является $\mathcal{NP}$-полной задачей.
\end{theorem}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

\begin{proof}
К задаче проверки совместности системы уравнений~$S_{M,2}$ над конечным матроидом~$M$ ранга~$2$ полиномиально сводится задача проверки совместности системы уравнений~$S_G$ над конечным полным $p$-дольным графом~$G$, которая $\mathcal{NP}$-полна по теореме~\ref{th1}.

В силу леммы~\ref{lem3} существует взаимно однозначно соответствие между классом матроидов ранга~$2$, все $1$-элементные множества которых независимы, и классом полных $p$-дольных графов.
Поэтому для определения совместности над графом~$G$ произвольной системы~$S_G$, состоящей из уравнений вида $E(x_i,x_j)$, $E(x_i,v_j)$, $E(v_i,v_j)$, $x_i=x_j$, $x_i=v_j$, ${v_i=v_j}$, достаточно определить, совместна ли над соответствующим ему матроидом~$M$ система~$S_{M,2}$, состоящая из уравнений вида $I_2(x_i,x_j)$, $I_2(x_i,v_j)$, $I_2(v_i,v_j)$, $x_i=x_j$, $x_i=v_j$, $v_i=v_j$, в~которой уравнения $I_2(t_i,t_j)$ и $t_i=t_j$ имеют место тогда и только тогда, когда соответствующие им уравнения $E(t_i,t_j)$ и $t_i=t_j$ содержатся в системе~$S_G$.

Таким образом, задача проверки совместности системы уравнений~$S_{M,2}$ над конечным матроидом~$M$ ранга~$2$ является $\mathcal{NP}$-полной.
\end{proof}

Поскольку задача проверки совместности системы уравнений~$S_{M,2}$ над конечным матроидом ранга~$2$ является частным случаем задачи проверки совместности системы уравнений~$S_{M,k}$ над конечным матроидом ранга, не превосходящего~$k$, то имеет место следствие из теоремы~\ref{th2}.

%Следствие 1
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{corollary}
\label{cor1}
Задача проверки совместности произвольной системы уравнений~$S_{M,k}$ над конечным матроидом ранга, не превосходящего~$k$, является $\mathcal{NP}$-полной задачей при $k \geqslant 2$.
\end{corollary}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\section{Совместность систем уравнений над однородными матроидами и матроидами разбиений}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Определим вычислительную сложность некоторых частных случаев задачи проверки совместности произвольной системы уравнений над конечными матроидами.
Рассмотрим наиболее простой класс матроидов~--- класс однородных матроидов.
Матроид называется {\it $k$-однородным}, если его базами являются все подмножества, содержащие ровно $k$~элементов.
Одним из подклассов класса конечных $k$-однородных матроидов является класс конечных $2$-однородных матроидов.
Легко заметить, что всякому $2$-однородному матроиду на $n$~элементах соответствует клика~$K_n$.
Таким образом, существует взаимно однозначное соответствие между классом $2$-однородных матроидов и классом всех клик.

%Теорема 3
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{theorem}
\label{th3}
Задача проверки совместности произвольной системы уравнений~$S_{M,2}$ над конечным $2$-однородным матроидом~$M$ является $\mathcal{NP}$-полной задачей.
\end{theorem}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

\begin{proof}
Аналогично доказательству теоремы~\ref{th2}.
К задаче проверки совместности системы уравнений~$S_{M,2}$ над конечным $2$-однородным матроидом~$M$ полиномиально сводится задача проверки совместности системы уравнений~$S_G$ над конечным полным $p$-дольным графом~$G$~--- в данном случае кликой~$K_n$, для которой $p=n$.
Эта задача является $\mathcal{NP}$-полной по теореме~\ref{th1}.
\end{proof}

Поскольку задача проверки совместности системы уравнений~$S_{M,2}$ над конечным $2$-однородным матроидом является частным случаем задачи проверки совместности системы уравнений~$S_{M,k}$ над конечным $k$-однородным матроидом, то имеет место следствие из теоремы~\ref{th3}.

%Следствие 2
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{corollary}
\label{cor2}
Задача проверки совместности произвольной системы уравнений~$S_{M,k}$ над конечным $k$-однородным матроидом является $\mathcal{NP}$-полной задачей при $k \geqslant 2$.
\end{corollary}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

В качестве ещё одного примера рассмотрим класс матроидов разбиения ранга, не превосходящего~$k$. 
Пусть ${P = \{U_1,U_2,...,U_k\}}$~--- разбиение множества $U$, т.\,е. $\bigcup\limits_{i=1}^{k} U_i = U$ и  
${U_i \cap U_j = \emptyset}$ для любых $i \not = j$.
Множество $I \subseteq U$ содержится в~${\mathcal I}_P$ тогда и только тогда, когда $|I \cap U_i| \leq 1$ для всех $i \in \{1,...,k\}$.
Тогда пара $M=(U,{\mathcal I}_P)$ является матроидом, который называется {\it матроидом разбиения} множества $U$, а ${\mathcal I}_P$~--- семейство его независимых подмножеств.

%Лемма 4
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{lemma}
\label{lem4}
Конечным матроидам ранга~$2$, все $1$-элементные множества которых независимы, взаимно однозначно соответствуют конечные матроиды разбиений.
\end{lemma}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

\begin{proof}
По лемме~\ref{lem3} конечные матроиды ранга~$2$, все $1$-элементные множества которых независимы, взаимно однозначно соответствуют конечным полным многодольным графам, у которых две вершины соединены ребром тогда и только тогда, когда соответствующее им $2$-элементное множество матроида независимо.
При этом полным многодольным графам взаимно однозначно соответствуют их дополнения~--- матроидные графы, которые в свою очередь взаимно однозначно соответствуют матроидам разбиений.
\end{proof}

%Предложение 2
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{proposition}
\label{pr2}
Множество $\{u_1,u_2\}$ независимо в матроиде разбиения тогда и только тогда, когда оно будет независимо в соответствующем ему матроиде ранга~$2$, все $1$-элементные множества которого независимы.
\end{proposition}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

%Предложение 3
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{proposition}
\label{pr3}
Любое $k$-элементное независимое множество матроида разбиения может быть получено из его $2$-элементных независимых множеств по следующему правилу:
$$
I_k(u_1,u_2,...,u_k) \longleftrightarrow I_2(u_1,u_2) \wedge I_2(u_1,u_3) \wedge ...  \wedge I_2(u_{k-1},u_k).
$$
\end{proposition}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

%Теорема 4
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{theorem}
\label{th4}
Задача проверки совместности произвольной системы уравнений~$S_{M,k}$ над конечным матроидом разбиения~$M$ ранга, не превосходящего~$k$, является $\mathcal{NP}$-полной задачей при $k \geqslant 3$.
\end{theorem}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

\begin{proof}
Очевидно, что частным случаем этой задачи является задача проверки совместности системы уравнений~$S_{M,2}$ над соответствующим матроиду разбиения~$M$ матроидом ранга~$2$, все $1$-элементные множества которого независимы, поскольку всякая система уравнений~$S_{M,2}$ совпадает с какой-то системой~$S_{M,k}$ при $k \geqslant 3$.
А такая задача является $\mathcal{NP}$-полной в силу теоремы~\ref{th2}.
\end{proof}

Отдельно рассмотрим случай, когда матроид разбиения имеет ранг $k=2$.

%Теорема 5
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{theorem}
\label{th5}
Задача проверки совместности произвольной системы уравнений~$S_{M,2}$ над конечным матроидом разбиения~$M$ ранга~$2$ является полиномиально разрешимой задачей.
\end{theorem}
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

\begin{proof}
Заметим, что каждому матроиду разбиения~$M$ ранга~$2$ соответствует полный двудольный граф~$G$.
При этом ранее было доказано, что существует полиномиальная процедура проверки совместности произвольной системы уравнений~$S_G$ над конечным полным двудольным графом~\cite{ii2021}.

Таким образом, для произвольной системы уравнений~$S_{M,2}$ можно за полиномиальное время проверить, совместна ли над матроидом~$M$ её подсистема, состоящая из всех уравнений вида $I_2(x_i,x_j)$, $I_2(x_i,u_j)$, $I_2(u_i,u_j)$, ${x_i=x_j}$, ${x_i=u_j}$, ${u_i=u_j}$.
Оставшиеся уравнения системы~$S_{M,2}$ имеют вид $I_0$, $I_1(x_i)$, $I_1(u_j)$ и в совокупности совместны над любым матроидом разбиений~$M$ по определению.
\end{proof}


\bigskip
\begin{thebibliography}{1} 

\bibitem{m1970} Y.V. Matiyasevich,
{\it Diophantineity of enumerable sets},
Doklady Akademii Nauk USSR, \textbf{191}:2 (1970), 279--282 (in Russian).

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

\bibitem{c1971} S.A. Cook,
{\it The complexity of theorem proving procedures},
Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, (1971), 151--158.

\bibitem{dmr2016} E.Y. Daniyarova, A.G. Myasnikov, V.N. Remeslennikov,
{\it Algebraic Geometry over Algebraic Structures},
SB RAS Publishing House, Novosibirsk, 2016 (in Russian).

\bibitem{nr2018} A.Y. Nikitin, A.N. Rybalov,
{\it On complexity of the satisfiability problem of systems over finite posets},
Prikladnaya Diskretnaya Matematika, {\bf 39} (2018), 94--98 (in Russian).

\bibitem{r2019} A.N. Rybalov,
{\it On complexity of the existential and universal theories of finite fields},
Prikladnaya Diskretnaya Matematika, {\bf 45} (2019), 85--89 (in Russian).

\bibitem{i2016n1} A.V. Ilev,
{\it Decidability of universal theories and axiomatizability of hereditary classes of graphs},
Trudy Instituta Matematiki i Mekhaniki UrO RAN, \textbf{22}:1 (2016), 100--111 (in Russian).

\bibitem{ir2017} A.V. Ilev, V.N. Remeslennikov,
{\it Study of the compatibility of systems of equations over graphs and finding their general solutions},
Vestnik Omskogo Universiteta, {\bf 4(86)} (2017), 26--32 (in Russian).

\bibitem{ii2021} A.V. Il’ev, V.P. Il’ev,
{\it Algorithms for solving systems of equations over various classes of finite graphs},
Prikladnaya Diskretnaya Matematika, {\bf 53} (2021), 89--102 (in Russian).

\bibitem{i2016n2} A.V. Iliev,
{\it On axiomatizability of hereditary classes of graphs and matroids},
Siberian Electronic Mathematical Reports, {\bf 13} (2016), 137--147.

\bibitem{ii2019} A.V. Il’ev, V.P. Il’ev,
{\it On axiomatizability and decidability of universal theories of hereditary classes of matroids},
Journal of Physics: Conference Series, {\bf 1210} (2019), 012056.

\bibitem{ii2020} A.V. Il’ev, V.P. Il’ev,
{\it On axiomatizability of the class of finitary matroids and decidability of their universal theory},
Siberian Electronic Mathematical Reports, {\bf 17} (2020), 1730--1740.

\bibitem{w1935} H. Whitney,
{\it On the abstract properties of linear dependence},
American Journal of Mathematics, {\bf 57} (1935), 509--533.

\bibitem{gj1982} M.R. Garey, D.S. Johnson,
{\it Computers and Intractability: A Guide to the Theory of NP-Completeness},
W.H. Freeman and Co, San Francisco, 1979.

\end{thebibliography}
\end{document}
