Минимаксные задачи дискретной оптимизации, инвариантные относительно мажоритарных операторов

Исследован специальный класс задач дискретной оптимизации, который сформулирован как минимаксная модификация проблемы непротиворечивости ограничений, известной в английской терминологии как Constraint satisfaction problem. Минимаксная формулировка задачи обобщает классическую задачу на реалистические ситуации, когда ограничения определяют не дихотомию множества на допустимое и недопустимое подмножества, а упорядочивают элементы множества по степени их допустимости. Определено понятие инвариантности этого упорядочивания относительно того или иного оператора и доказана полиномиальная сложность дискретной минимизации функций, инвариантных относительно мажоритарных операторов. Приводится конкретный алгоритм этой минимизации. Библ. 6.