О сложности метода последовательного опробования

Система $m$ булевых уравнений может быть решена методом последовательного опробования с помощью $m$-шагового алгоритма, где на $i$-м шаге опробуются значения всех переменных, существенных для первых $i$ уравнений, и ложные решения отбраковываются по правым частям уравнений, $i=1,\dots,m$. Оценка сложности метода, зависящая от структуры множеств существенных переменных уравнений, достигает минимума при некоторых перестановках уравнений системы. Предложен алгоритм оптимальной перестановки уравнений, минимизирующей среднюю вычислительную сложность алгоритма в естественных вероятностных предположениях. В ряде случаев оптимальные перестановки определены неоднозначно, и их нахождение является вычислительно сложным. Метод последовательного опробования вырождается в полный перебор, если каждое уравнение системы зависит существенно от всех переменных. Приведён пример построения оптимальной перестановки. Табл. 2, ил. 1, билиогр. 11.