Совместность и алгоритм распознавания несовместности реализаций случайных систем дискретных уравнений с двузначными неизвестными

Рассматривается случайная система дискретных уравнений относительно $n$ двузначных неизвестных, состоящая из $M=M(n)$ уравнений. Функции в уравнениях выбираются случайно из конечного множества функций и могут зависеть не более чем от $m$ переменных. Обоснован критерий наличия у случайной системы уравнений пороговой функции совместности, определяемой как функция $Q(n)$, для которой вероятность совместности случайной системы уравнений стремится к единице и к нулю при $n\to\infty$, $M(n)/Q(n)\to0$ и $M(n)/Q(n)\to\infty$. Показано, что пороговые функции совместности могут иметь только вид $n$ и $n^{1-1/r}$, $2\le r\le m+1$; построены критерии наличия у случайной системы уравнений таких пороговых функций. Для случайных систем уравнений с пороговыми функциями вида $n^{1-1/r}$, $2\le r\le m+1$, оценена вероятность совместности при $M\sim cn^{1-1/r}$, $n\to\infty$ (она убывает от единицы до нуля, принимая все промежуточные значения, с ростом $c$ от нуля до $\infty$) и построен алгоритм распознавания несовместности реализаций случайных систем уравнений. Этот алгоритм имеет такую же предельную вероятность определения несовместности систем уравнений, как и алгоритм полного перебора решений, но низкую трудоемкость – порядка $n^{1-1/r}$.