|
Совместность случайных систем уравнений с неравновероятной выборкой двузначных неизвестных
А. В. Шаповалов Лаборатория ТВП, Москва
Аннотация:
Рассматривается случайная система уравнений относительно $n$ двузначных неизвестных, состоящая из $M=M(n)$ уравнений. Каждое уравнение содержит не более $m$ неизвестных, которые выбираются случайно и независимо. Указаны условия, при которых предельное при $M=cn^{1-1/r}+o(n^{1-1/r})$, $n\to\infty$, $2\le r\le m+1$, $m=\mathrm{const}$, значение вероятности совместности убывает от 1 до 0 с ростом $c$ от 0 до $\infty$. Построен алгоритм распознавания несовместности случайной системы уравнений, имеющий при этих условиях трудоемкость $O(n^{1-1/r})$, $2\le r\le m+1$, и асимптотически такую же вероятность распознавания несовместности как для алгоритма полного перебора.
Ключевые слова:
системы дискретных уравнений, совместность, вероятностные алгоритмы, случайные гиперграфы.
Получено 01.XI.2010
Образец цитирования:
А. В. Шаповалов, “Совместность случайных систем уравнений с неравновероятной выборкой двузначных неизвестных”, Матем. вопр. криптогр., 2:4 (2011), 109–146
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mvk46https://doi.org/10.4213/mvk46 https://www.mathnet.ru/rus/mvk/v2/i4/p109
|
Статистика просмотров: |
Страница аннотации: | 327 | PDF полного текста: | 204 | Список литературы: | 42 | Первая страница: | 1 |
|