Задача о разбиении: различия между версиями

'''Задача о разбиении''' (''Partitioning problem'') -  

одна из основных ''<math>\cal NP</math>-полных'' задач.

Формулируется следующим образом.

Существует ли разбиение данного конечного множества

элементов, имеющих неотрицательный вес, на два подмножества, равных по

суммарному весу составляющих их элементов?

См. также ''Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы <math>\cal P</math> и <math>\cal NP</math>, Метод локальной замены, Метод построения компонент, Метод сужения задачи, Полиномиальная сводимость (трансформируемость), <math>\cal NP</math>-полная задача, Труднорешаемая задача.''