|
Эта публикация цитируется в 1 научной статье (всего в 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)$. Предел вероятности распознавания несовместности для этого алгоритма такой же, как для алгоритма полного перебора. Доказательства используют геометрические свойства случайной системы уравнений.
Ключевые слова:
системы дискретных уравнений, неразрешимость, вероятностные алгоритмы.
Получено 22.IV.2010
Образец цитирования:
А. В. Шаповалов, “Характеристики случайных систем дискретных уравнений при неравновероятной выборке неизвестных”, Матем. вопр. криптогр., 1:3 (2010), 93–117
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mvk17https://doi.org/10.4213/mvk17 https://www.mathnet.ru/rus/mvk/v1/i3/p93
|
Статистика просмотров: |
Страница аннотации: | 376 | PDF полного текста: | 207 | Список литературы: | 49 | Первая страница: | 1 |
|