О сложности метода последовательного опробования
В. М. Фомичёвab a ООО «Код Безопасности», 1-й Нагатинский пр-д, 10, стр. 1, 115230 Москва, Россия
b Институт проблем информатики ФИЦ «Информатика и управление» РАН, ул. Вавилова, 44, корп. 2, 119333 Москва, Россия
Аннотация:
Система
$m$ булевых уравнений может быть решена методом последовательного опробования с помощью
$m$-шагового алгоритма, где на
$i$-м шаге опробуются значения всех переменных, существенных для первых
$i$ уравнений, и ложные решения отбраковываются по правым частям уравнений,
$i=1,\dots,m$. Оценка сложности метода, зависящая от структуры множеств существенных переменных уравнений, достигает минимума при некоторых перестановках уравнений системы. Предложен алгоритм оптимальной перестановки уравнений, минимизирующей среднюю вычислительную сложность алгоритма в естественных вероятностных предположениях. В ряде случаев оптимальные перестановки определены неоднозначно, и их нахождение является вычислительно сложным. Метод последовательного опробования вырождается в полный перебор, если каждое уравнение системы зависит существенно от всех переменных. Приведён пример построения оптимальной перестановки. Табл. 2, ил. 1, билиогр. 11.
Ключевые слова:
булева функция, существенная переменная, решётка подмножеств множества, цепь в решётке.
УДК:
519.17 Статья поступила: 30.03.2023
Переработанный вариант: 17.10.2023
Принята к публикации: 22.12.2023
DOI:
10.33048/daio.2024.31.766