О минимизации булевых функций для аддитивных мер сложности

Задача минимизации булевых функций для аддитивных мер сложности в геометрической интерпретации, как покрытие гранями подмножества вершин в единичном кубе, является специальным видом комбинаторной постановки взвешенной задачи о минимальном покрытии множества. Специфика определяется семейством покрывающих подмножеств, которые являются гранями в единичном кубе и содержатся в множестве единичных вершин функции, и мерой сложности граней, которая задаёт вес граней при вычислении сложности покрытия. Для меры сложности требуется неотрицательность, монотонность по включению граней и равенство для изоморфных граней. Для аддитивных мер сложности вводится классификация по порядку роста сложности граней в зависимости от размерности куба и исследуются характеристики сложности минимизации почти всех булевых функций. Библиогр. 11.