Об одном методе решения систем квадратичных булевых уравнений, использующем локальные аффинности

Как известно, вычислительная задача решения систем нелинейных уравнений над полем из двух элементов является NP-трудной. Этим обстоятельством обусловливается стремление исследователей разрабатывать алгоритмы ее решения, минимизирующие необходимые вычислительные ресурсы для тех или иных классов систем уравнений. В статье предлагается метод решения систем квадратичных булевых уравнений, использующий представление функций их аффинными нормальными формами, т. е. в некотором смысле аппроксимацию квадратичных функций кусочно-аффинными. Для каждого уравнения на основе такого представления строится набор систем небольшого числа линейных уравнений, а затем ищется совместная комбинация этих линейных систем для различных исходных уравнений. Исходная нелинейная задача, таким образом, сводится, по большому счету, к проверке совместности серии линейных систем от того же числа переменных. Метод может быть эффективно распараллелен и, несмотря на большую трудоемкость в худшем случае, допускает ряд эвристик, уменьшающих время его выполнения.