Обобщение задачи о сумме подмножеств и кубические формы

Предложен новый алгоритм для распознавания существования двоичного решения у системы линейных уравнений над полем нулевой характеристики, который эффективен при выполнении некоторого ограничения на систему уравнений. Это частный случай задачи целочисленного программирования. В расширенной версии задачи о сумме подмножеств вес может быть как положительным, так и отрицательным. Рассмотренная нами задача эквивалентна задаче о существовании решения для нескольких частных случаев этой задачи одновременно. Найдены новые достаточные условия, при которых вычислительная сложность почти всех частных случаев такой задачи полиномиальная. По сути, алгоритм проверяет, существует ли кубическая гиперповерхность, проходящая через каждую вершину единичного куба, но не пересекающая заданное аффинное подпространство. Ранее уже было известно несколько эвристических алгоритмов для решения этой задачи. Однако новые методы расширяют возможности для решения тех или иных задач. Хотя подробно рассмотрена лишь задача распознавания, бинарный поиск позволяет найти решение, если это возможно.
Библ. 40.