Является ли мой алгоритм сумм подмножеств полиномиального времени?

Question

Я придумал новый алгоритм для решения проблемы суммы подмножеств , и я думаю, что это за полиномиальное время.Скажите мне, что я либо не прав, либо полностью гениален.

Быстрые факты для начала:

Проблема с подмножеством суммы - это полная проблема NP.Решение за полиномиальное время означает, что P = NP.
Количество подмножеств в наборе длины N равно 2 ^ N.

С более полезной стороны, число уникальных подмножеств в длине N максимальносумма всего набора минус наименьший элемент, или диапазон сумм, которые может произвести любое подмножество, находится между суммой всех отрицательных элементов и суммой всех положительных элементов, поскольку никакая сумма не может быть больше или меньше, чемвсе положительные или отрицательные суммы, которые растут с линейной скоростью, когда мы добавляем дополнительные элементы.

Это означает, что при увеличении N количество повторяющихся подмножеств увеличивается экспоненциально, а количество уникальных, полезных подмножествувеличивается только линейно.Если бы можно было разработать алгоритм, который мог бы удалить дублирующиеся подмножества при первой же возможности, мы бы работали за полиномиальное время.Быстрый пример легко берется из двоичного файла.Только из чисел, являющихся степенями двух, мы можем создать уникальные подмножества для любого интегрального значения.Таким образом, любое подмножество, включающее любое другое число (если у нас было все полномочия двух), является дубликатом и пустой тратой.Не вычисляя их и их производные, мы можем сэкономить практически все время работы алгоритма, поскольку числа, являющиеся степенями двух, логарифмически встречаются по сравнению с любым целым числом.

В связи с этим я предлагаю простой алгоритмэто удалит эти дубликаты и избавит от необходимости вычислять их и все их производные.

Для начала, мы отсортируем множество, которое является только O (N log N), и разделим его на две половины, положительныеи отрицательный.Процедура для отрицательных чисел идентична, поэтому я выделю только положительные числа (теперь набор означает только положительную половину, просто для пояснения).

Представьте массив, проиндексированный по сумме, в котором есть записи длявсе возможные итоговые суммы положительной стороны (помните, что она только линейная).Когда мы добавляем запись, значение - это записи в подмножестве.Например, array [3] = {1, 2}.

В общем, теперь мы переходим к перечислению всех подмножеств в наборе.Мы делаем это, начиная с подмножеств одной длины, затем добавляя к ним.Когда у нас есть все уникальные подмножества, они образуют массив, и мы просто повторяем их в порядке, используемом в Horowitz / Sahni.

Теперь мы начнем со значений «первого поколения».То есть, если в исходном наборе данных не было дубликатов, в этих значениях гарантированно не было дубликатов.То есть все подмножества с одним значением и вся длина набора минус одно подмножество длины.Их можно легко сгенерировать, суммируя множество и вычитая каждый элемент по очереди.Кроме того, сам набор является действительной суммой и подмножеством первого поколения, а также каждым отдельным элементом подмножества.

Теперь мы делаем значения второго поколения.Мы перебираем каждое значение в массиве и для каждого уникального подмножества, если его нет, мы добавляем его и вычисляем новое уникальное подмножество.Если у нас есть дубликат, веселье происходит.Мы добавляем его в список столкновений.Когда мы добавляем новые подмножества, мы проверяем, есть ли они в списке столкновений.Мы используем менее желательное (обычно большее, но может быть произвольное) равное подмножество.Когда мы добавляем к подмножествам, если мы генерируем коллизию, мы просто ничего не делаем.Когда мы добавляем более желательное подмножество, оно пропускает проверку и добавляет, генерируя общее подмножество.Тогда мы просто повторяем для других поколений.

Удаляя дублирующиеся подмножества таким образом, нам не нужно ни комбинировать дубликаты с остальной частью набора, ни проверять их на наличие коллизий, ни суммировать их.Что наиболее важно, не создавая новые не подмножества, мы не генерируем из них новые подмножества, которые, я полагаю, могут повернуть алгоритм с NP на P, поскольку рост подмножеств больше не экспоненциальный - мы отбрасываемподавляющее большинство из них прежде, чем они смогут «воспроизвести» в следующем поколении и создать больше подмножеств, комбинируя их с другими неповторяющимися подмножествами.

Не думаю, что я объяснил это слишком хорошо.У меня есть картинки ... они у меня в голове.Важно то, что, отбрасывая дублированные подмножества, вы можете удалить практически все сложности.

Например, представьте (потому что я делаю этот пример вручную) простой набор данных, который идет от -7 до 7 (не ноль) для которого мы стремимся к нулю.Сортировка и разделение, так что мы остались с (1, 2, 3, 4, 5, 6, 7).Сумма равна 28. Но 2 ^ 7 - это 128. Таким образом, 128 подмножеств вписываются в диапазон 1 ... 28, что означает, что мы заранее знаем, что 100 наборов являются дубликатами.Если бы у нас было 8, то у нас было бы только 36 слотов, а теперь 256 подмножеств.Таким образом, вы можете легко увидеть, что число дублирований теперь будет 220, что вдвое больше, чем было раньше.

В этом случае значения первого поколения равны 1, 2, 3, 4, 5, 6,7, 28, 27, 26, 25, 24, 23, 22, 21, и мы сопоставляем их с составляющими их компонентами, поэтому

1 = { 1 }
2 = { 2 }
...
28 = { 1, 2, 3, 4, 5, 6, 7 }
27 = { 2, 3, 4, 5, 6, 7 }
26 = { 1, 3, 4, 5, 6, 7 }
...
21 = { 1, 2, 3, 4, 5, 6 }

Теперь, чтобы сгенерировать новые подмножества, мы берем каждое подмножество по очередии добавьте его друг к другу в подмножество, если только они не имеют взаимного подмножества, например, 28 и 27 не имеют взаимного подмножества hueg.Поэтому, когда мы берем 1 и добавляем его к 2, мы получаем 3 = {1, 2}, но теперь ждем!Это уже в массиве.Это означает, что мы теперь не добавляем 1 к любому подмножеству, в котором уже есть 2, и наоборот, потому что это дубликат на 3 подмножествах.

Теперь у нас есть

1 = { 1 }
2 = { 2 }
// Didn't add 1 to 2 to get 3 because that's a dupe
3 = { 3 } // Add 1 to 3, amagad, get a duplicate. Repeat the process.
4 = { 4 } // And again.
...
8 = { 1, 7 }

21? Already has 1 in.
...
27? We already have 28

Теперь мы добавляем 2 ко всем.

1? Existing duplicate
3? Get a new duplicate
...
9 = { 2, 7 }
10 = { 1, 2, 7 }

21? Already has 2 in
...
26? Already have 28
27? Got 2 in already.

3?

1? Existing dupe
2? Existing dupe
4? New duplicate
5? New duplicate
6? New duplicate
7? New duplicate
11 = { 1, 3, 7 }
12 = { 2, 3, 7 }
13 = { 1, 2, 3, 7 }

Как вы можете видеть, хотя я все еще добавляю новые подмножества каждый раз, количество только увеличиваетсялинейно.

4?

1? Existing dupe
2? Existing dupe
3? Existing dupe
5? New duplicate
6? New duplicate
7? New duplicate
8? New duplicate
9? New duplicate
14 = {1, 2, 4, 7}
15 = {1, 3, 4, 7}
16 = {2, 3, 4, 7}
17 = {1, 2, 3, 4, 7}

5?

1,2,3,4 existing duplicate
6,7,8,9,10,11,12 new duplicate
18 = {1, 2, 3, 5, 7}
19 = {1, 2, 4, 5, 7}
20 = {1, 3, 4, 5, 7}
21 = new duplicate

Теперь у нас есть все значения в диапазоне, поэтому мы остановимся и добавим в наш список 1-28.Повторите эти действия для отрицательных чисел, просматривайте списки.

Редактировать:

Этот алгоритм в любом случае совершенно неверен.Подмножества, имеющие повторяющиеся суммы, являются , а не дубликатами, для которых из них можно порождать подмножества, поскольку они получены по-разному, т. Е. Они не могут быть сложены.

Answer 1

Это не доказывает P = NP.

Вы не рассмотрели возможность, когда положительные числа: 1, 2, 4, 8, 16 и т. Д. И т. Д.дублирует при суммировании подмножеств, поэтому в этом случае он будет выполняться за O (2 ^ N).

Вы можете рассматривать это как особый случай, но алгоритм все еще не является полиномиальным для других подобных случаев.Это предположение, которое вы сделали, заключается в том, что вы уходите от NP-полной версии суммы подмножества к решению только простых (полиномиальных) задач:линейная скорость, когда мы добавляем дополнительные элементы.

Здесь вы фактически предполагаете, что P (то есть количество битов, необходимых для постановки задачи) меньше, чем N. Цитата из Википедии:

Таким образом, проблема является наиболее сложной, если N и P имеют одинаковый порядок.

Если вы предполагаете, что N и P имеют одинаковый порядок, то вы не можете предположить, что суммарастет линейно до бесконечности по мере добавления новых элементов.Когда вы добавляете больше элементов к вашему набору, эти элементы также должны увеличиваться, чтобы гарантировать, что проблему по-прежнему трудно решить.

Если P (число значений места) является небольшим фиксированным числом, тоявляются алгоритмами динамического программирования, которые могут точно его решить.

Вы заново открыли один из этих алгоритмов.Это хорошая работа, но это не что-то новое и не доказывает P = NP.Извините!

Answer 2

Dead MG,

Прошло почти полгода с тех пор, как вы написали, но я все равно отвечу.

Марк Байерс написал большую часть того, что должно быть написано.

Алгоритм известен.

Такие алгоритмы известны как алгоритмы генерирующих функций или просто как алгоритмы динамического программирования.

Ваш алгоритм имеет очень важную особенность, так называемую псевдополиномиальную сложность.

Традиционная сложность зависит от размера проблемы. В терминах традиционной сложности ваш алгоритм имеет O (2 ^ n) пессимистическую сложность (то есть для чисел 1,2, 4, ..., как упоминалось ранее)

Сложность алгоритма вашего алгоритма может быть альтернативно выражена как функция размера задачи и размера некоторых чисел в задаче. Для вашего алгоритма это будет что-то вроде O (nw), где w - количество различных сумм.

Это псевдополиномиальная сложность. Это очень важная особенность. Такие алгоритмы могут решить множество реальных проблемных случаев, несмотря на класс сложности проблемы.

Алгоритм Горовица и Сахни имеет пессимистическую сложность O (2 ^ N / 2). Это не в два раза лучше, чем ваш алгоритм, но намного больше - в 2 ^ N / 2 раза лучше, чем ваш алгоритм. Что Грег, вероятно, имел в виду, так это то, что алгоритм Горовица и Сахни может решить в два раза большие случаи проблемы (имея вдвое больше чисел в сумме подмножеств)

Это верно в теории, но на практике Горовиц и Сахни могут решать (на домашних компьютерах) экземпляры с примерно 60 числами, в то время как алгоритм, аналогичный вашему, может обрабатывать даже экземпляры с 1000 числами (при условии, что сами числа не слишком велики) ) * * тысяча двадцать-один

На самом деле два алгоритма могут быть даже смешаны, это ваш тип алгоритма Горовица и Сахни. Такое решение имеет как псевдополиномиальную сложность, так и пессимистическую сложность O (2 ^ n / 2).

Опытный компьютерный ученый может построить такой алгоритм, как ваш, с помощью теории порождающих функций.

Как обученные, так и неподготовленные могут думать так же, как вы.

Не обязательно думать в терминах "это известно?" Для вас должно быть важно, что вы можете придумать такой алгоритм самостоятельно. Это означает, что вы, вероятно, можете придумать другие важные алгоритмы самостоятельно и когда-нибудь, возможно, неизвестно. Знание текущих достижений в этой области и того, что в литературе, помогает. В противном случае вы будете продолжать изобретать велосипед.

Когда я был в старшей школе, я заново изобрел алгоритм Дейкстры. Моя версия имела ужасную сложность, потому что я ничего не знал о структурах данных. Во всяком случае, я все еще горжусь собой.

Если вы все еще учитесь, обратите внимание на теорию порождающих функций.

Вы также можете проверить на вики:

псевдополиномиальное время слабо NP-полный сильно NP-полный генерирующие функции

Megli

Answer 3

Это означает, что при увеличении N количество повторяющихся подмножеств увеличивается экспоненциально, а количество уникальных полезных подмножеств увеличивается только линейно.

Не обязательно - количество повторяющихся сумм подмножеств также определяется значением числа, ближайшего к нулю в наборе (чем больше минимальное расстояние до нуля, тем меньше сумм повторяющихся подмножеств для набора).

В общем, теперь мы переходим к перечислению всех подмножеств в наборе.

К сожалению, перечисление всех сумм подмножеств набора требует выполнения экспоненциального числа операций сложения (2 ^ 7 или 128 в вашем примере). В противном случае, как алгоритм определит, какими будут уникальные суммы? Таким образом, хотя шаги, которые следуют за первым шагом, вполне могут иметь полиномиальное время выполнения, алгоритм в целом имеет экспоненциальную сложность (поскольку алгоритм работает так же быстро, как и его самая медленная часть).

Между прочим, самый известный алгоритм для решения проблемы суммы подмножеств (Horowitz and Sahni, 1974) имеет сложность O (2 ^ N / 2) - что делает его примерно в два раза быстрее, чем этот алгоритм.