Об одном методе решения систем квадратичных булевых уравнений, использующем локальные аффинностистатья
Статья опубликована в журнале из списка RSCI Web of Science
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 1 апреля 2020 г.
Аннотация:Как известно, вычислительная задача решения систем нелинейных уравнений над полем из двух элементов является NP-трудной. Этим обстоятельством обусловливается стремление исследователей разрабатывать алгоритмы ее решения, минимизирующие необходимые вычислительные ресурсы для тех или иных классов систем уравнений. В статье предлагается метод решения систем квадратичных булевых уравнений, использующий представление функций их аффинными нормальными формами, т. е. в некотором смысле аппроксимацию квадратичных функций кусочно-аффинными. Для каждого уравнения на основе такого представления строится набор систем небольшого числа линейных уравнений, а затем ищется совместная комбинация этих линейных систем для различных исходных уравнений. Исходная нелинейная задача, таким образом, сводится, по большому счету, к проверке совместности серии линейных систем от того же числа переменных. Метод может быть эффективно распараллелен и, несмотря на большую трудоемкость в худшем случае, допускает ряд эвристик, уменьшающих время его выполнения.