Эта публикация цитируется в
1 статье
Характеристики случайных систем дискретных уравнений при неравновероятной выборке неизвестных
А. В. Шаповалов Лаборатория ТВП, Москва
Аннотация:
Изучается случайная система дискретных уравнений
$S$ относительно
$n$ неизвестных, состоящая из
$M=M(n)$ уравнений. Каждое уравнение содержит не более
$m$ неизвестных, которые выбираются случайно, независимо и, вообще говоря, неравновероятно. Указаны условия, при которых предельное при
$M-c\sqrt n=o(\sqrt n)$,
$n\to\infty$,
$m=\operatorname{const}$ значение вероятности совместности случайной системы уравнений непрерывно убывает от
$1$ до
$0$ с ростом
$c$ от
$0$ до
$\infty$. Построен алгоритм распознавания несовместности случайной системы уравнений, имеющий трудоемкость
$O(\sqrt n)$. Предел вероятности распознавания несовместности для этого алгоритма такой же, как для алгоритма полного перебора. Доказательства используют геометрические свойства случайной системы уравнений.
Ключевые слова:
системы дискретных уравнений, неразрешимость, вероятностные алгоритмы.
УДК:
519.212.2 Получено 22.IV.2010
DOI:
10.4213/mvk17