Введение
Проблема 3-го раздела является сильной NP-полной проблемой в информатике. Проблема заключается в том, чтобы решить, может ли данное множество целых чисел быть разделено на тройки, которые имеют одинаковую сумму. Более точно: Вход: многомножество S, содержащее n положительных элементов целого числа. Условия: S должно быть делимо на m тройниц, S1, S2, Sm, где n = 3m. Эти тройни разделяют S в том смысле, что они не соединены и покрывают S. Целевое значение T вычисляется путем принятия суммы всех элементов в S, затем деленного на m. Выход: существует ли такой раздел S, чтобы для всех тройни сумма элементов в каждом тройнике равнялась T. Проблема разделения 3 остается полностью NP-полной при ограничении, что каждое целое число в S находится строго между T/4 и T/2.
Input: a multiset S containing n positive integer elements. Conditions: S must be partitionable into m triplets, S1, S2, , Sm, where n = 3m. These triplets partition S in the sense that they are disjoint and they cover S. The target value T is computed by taking the sum of all elements in S, then divided by m.
Output: whether or not there exists a partition of S such that, for all triplets, the sum of the elements in each triplet equals T.
The 3 partition problem remains strongly NP complete under the restriction that every integer in S is strictly between T/4 and T/2.
Пример
Множество можно разделить на четыре множества , каждая из которых составляет T = 90. Множество можно разделить на два множества, каждая из которых составляет T = 15. (каждое целое число в S находится строго между T/4 и T/2): , таким образом m=2, и T=15. Есть 3 возможных раздела (каждое целое число в S находится строго между T/4 и T/2): , таким образом, m=2, и T=15. Нет никакого реального решения.
Сильная NP-полнота
Проблема разделения 3 остается NP-полной даже тогда, когда целые числа в S ограничены выше полиномием в n. Другими словами, проблема остается NP-полной даже при представлении чисел в входном экземпляре в униарном. т.е. разделение 3 является NP-комплектным в сильном смысле или сильно NP-комплектным. Это свойство, и 3 разделения в целом, полезно во многих сокращениях, где числа естественным образом представлены в униарном.
3-Партирование против разделения
Проблема разделения 3 похожа на проблему разделения, в которой целью является разделение S на два подмножества с равной суммой, и многостороннее разделение числа, в котором целью является разделение S на k подмножеств с равной суммой, где k является фиксированным параметром. В разделе 3 цель состоит в том, чтобы разделить S на m = n/3 подмножеств, а не просто на фиксированное количество подмножеств с равной суммой. Разделение "легче" чем 3 Разделение: в то время как 3 Разделение является сильно NP-трудным, Разделение является только слабо NP-трудным. Это трудно только тогда, когда числа закодированы в не униальной системе и имеют значение экспоненциальное в n. Когда значения являются многочленными в n, Разделение может быть решено в многочленное время с использованием алгоритма разделения чисел в псевдополиномное время.
Варианты
В неограниченном варианте ввода входные данные могут быть произвольными целыми числами; в ограниченном варианте ввода входные данные должны быть в (T/4, T/2). Ограниченная версия так же сложна, как и неограниченная: если дается экземпляр Su неограниченного варианта, создать новый экземпляр ограниченной версии }. Каждое решение Su соответствует решению Sr, но с суммой 7 вместо T, и каждый элемент Sr, содержащийся в In в различном варианте входа, входные данные должны быть в (T/4, T/2), и, кроме того, все они должны быть различными целыми числами. Она также так же сложна, как и не ограниченная версия. В неограниченном варианте вывода, m вывода подмножества могут быть произвольного размера не обязательно 3 (но они все равно должны иметь ту же сумму T). Ограниченный вариант выхода может быть сведен к неограниченному варианту: с учетом экземпляра Sr ограниченного варианта, с 3 м элементами, суммирующими до mT, создать новый экземпляр неограниченного варианта }, с 3 м элементами, суммирующими до 7 мT, и с целевой суммой 7. Каждому раствору Sr естественно соответствует раствор Su. И наоборот, в каждом решении Su, поскольку целевая сумма равна 7 и каждый элемент находится в , должно быть ровно 3 элемента в наборе, поэтому это соответствует решению Sr. Проблема разделения ABC (также называемая числовым 3d соответствием) - это вариант, в котором вместо множества S с 3 целыми числами, есть три множества A, B, C с m целыми числами в каждом. Сумма чисел во всех множествах равна m T. Цель состоит в том, чтобы построить m троек, каждая из которых содержит один элемент из A, один из B и один из C, таким образом, что сумма каждого тройки равна T. Проблема разделения 4 представляет собой вариант, в котором S содержит n = 4 целых числа, сумма всех целых чисел равна m T, и цель состоит в том, чтобы разделить его на m четвертиков, все с суммой T. Можно предположить, что каждое целое число находится строго между T/5 и T/3. Аналогичным образом, ABCD parititon - это вариант 4-х разделов, в котором каждый имеет 4 входных множества, и каждый квадроплет должен содержать один элемент из каждого множества.
In the distinct input variant, the inputs must be in (T/4, T/2), and in addition, they must all be distinct integers. It, too, is as hard as the unrestricted version. In the unrestricted output variant, the m output subsets can be of arbitrary size not necessarily 3 (but they still need to have the same sum T). The restricted output variant can be reduced to the unrestricted variant: given an instance Sr of the restricted variant, with 3m items summing up to mT, construct a new instance of the unrestricted variant }, with 3m items summing up to 7mT, and with target sum 7. Every solution of Sr naturally corresponds to a solution of Su. Conversely, in every solution of Su, since the target sum is 7 and each element is in , there must be exactly 3 elements per set, so it corresponds to a solution of Sr. The ABC partition problem (also called numerical 3 d matching) is a variant in which, instead of a set S with 3 integers, there are three sets A, B, C with m integers in each. The sum of numbers in all sets is m T. The goal is to construct m triplets, each of which contains one element from A, one from B and one from C, such that the sum of each triplet is T.
The 4 partition problem is a variant in which S contains n = 4 integers, the sum of all integers is m T, and the goal is to partition it into m quadruplets, all with a sum of T. It can be assumed that each integer is strictly between T/5 and T/3. Similarly, ABCD parititon is a variant of 4 partition in which each there are 4 input sets and each quadruplet should contain one element from each set.
Доказательства
Грей и Джонсон (1975) первоначально доказали, что 3 Partition является NP-полным, путем уменьшения из 3-мерного соответствия. Классическая ссылка Гари и Джонсона (1979) описывает доказательство NP-полноты, сокращая от 3-мерного соответствия до 4-го раздела до 3-го раздела. Логически, сокращение можно разделить на несколько этапов.
Приложения
Твердость NP 3 разделов использовалась для доказательства твердости NP прямоугольника, а также Tetris и некоторых других головоломок, а также некоторых задач по планированию задач.