Аннотация:
Изучается случайная система дискретных уравнений S относительно n неизвестных, состоящая из M=M(n) уравнений. Каждое уравнение содержит не более m неизвестных, которые выбираются случайно, независимо и, вообще говоря, неравновероятно. Указаны условия, при которых предельное при M−c√n=o(√n), n→∞, m=const значение вероятности совместности случайной системы уравнений непрерывно убывает от 1 до 0 с ростом c от 0 до ∞. Построен алгоритм распознавания несовместности случайной системы уравнений, имеющий трудоемкость O(√n). Предел вероятности распознавания несовместности для этого алгоритма такой же, как для алгоритма полного перебора. Доказательства используют геометрические свойства случайной системы уравнений.
Ключевые слова:
системы дискретных уравнений, неразрешимость, вероятностные алгоритмы.
Получено 22.IV.2010
Тип публикации:
Статья
УДК:519.212.2
Образец цитирования:
А. В. Шаповалов, “Характеристики случайных систем дискретных уравнений при неравновероятной выборке неизвестных”, Матем. вопр. криптогр., 1:3 (2010), 93–117
\RBibitem{Sha10}
\by А.~В.~Шаповалов
\paper Характеристики случайных систем дискретных уравнений при неравновероятной выборке неизвестных
\jour Матем. вопр. криптогр.
\yr 2010
\vol 1
\issue 3
\pages 93--117
\mathnet{http://mi.mathnet.ru/mvk17}
\crossref{https://doi.org/10.4213/mvk17}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mvk17
https://doi.org/10.4213/mvk17
https://www.mathnet.ru/rus/mvk/v1/i3/p93
Эта публикация цитируется в следующих 1 статьяx:
А. В. Шаповалов, “Совместность случайных систем уравнений с неравновероятной выборкой двузначных неизвестных”, Матем. вопр. криптогр., 2:4 (2011), 109–146