Некоторые классы эффективно решаемых систем булевых уравнений

Пусть $\Gamma$ – множество ориентированных ациклических корневых графов, для которых существует взаимно однозначное соответствие между путями максимальной длины и $n$-мерными векторами. Оно позволяет каждому ребру графа $G\in\Gamma_n$ сопоставить булеву функцию, равную единице только на векторах, соответствующих путям, проходящим через это ребро. Такие функции порождают $Z$-модуль над кольцом $Z$ целых чисел, обозначаемый $L_Z(G)$.
Дается описание функций $f(\vec x)\in L_Z(G)$, булевых функций, принадлежащих модулю $L_Z(G)$, и множества $B(G)$ булевых функций, являющихся “булевыми проекциями” функций из $L_Z(G)$. Показано, что решение системы булевых уравнений
$$ \varphi_i(x_1,\dots,x_n)=0,\quad i=\overline{1,t}, $$
где $\varphi_i(\vec x)\in B(G)$, $i=\overline{1,t}$, а также нахождение оценки максимального правдоподобия решения системы булевых уравнений с искаженной правой частью
$$ \varphi_i(x_1,\dots,x_n)=a_i\otimes\varepsilon,\quad i=\overline{1,t}, $$
где $\varphi_i(\vec x)\in L_Z(G)$, $i=\overline{1,t}$, сводится к нахождению булевого вектора $\vec a$, минимизирующего значение некоторой функции $f(\vec x)\in L_Z(G)$. Эта задача имеет характеристики сложности и памяти, линейно зависящие от числа вершин графа $G$. Указанное сведение можно осуществить для любой системы уравнений рассматриваемого вида.