2010-01-03 19 views
2

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

Например ((1,2,4,5),6) является true, потому что (2,4) суммы к 6. Мы говорим, что (2,4) является "solution"

Кроме того, ((1,5,10),7) является false, потому что ничто в аргументах не подводить к 7

Мой вопрос, учитывая набор чисел аргументов для SUBSET-SUM есть полином верхняя граница числа возможные решения. В первом примере были (2,4) и (1,5).

Мы знаем, что с SUBSET-SUM является NP-полным решением в полиномное время, вероятно, невозможно. Однако мой вопрос не связан с временем принятия решения, я строго спрашиваю о размере списка решений.

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

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

+0

mathoverflow.com? – JonH

+0

Рассмотрим '((2 2 2 2 2 2 2 2 2 2) 10)'. Здесь есть 252 комбинации из 5 2, которые вы можете выбрать, чтобы получить 10. Если вы считаете ответы с одинаковыми номерами, но разные индексы одинаковы, то в этом случае есть только одно решение. Не могли бы вы сосчитать выше 252 решения или всего 1? –

+0

1, я должен был упомянуть, что меня интересуют уникальные решения. – Mike

ответ

2

Нет; принять номера:

(1, 2, 1 + 2, 4, 8, 4 + 8, 16, 32, 16 + 32, ..., 2 2n, 2 2n + 1, 2 2n + 22n + 1)

и спросить о формировании сумма 1 + 2 + 4 + ... 2 2n + 22n + 1. (Например: при n = 3 возьмите набор (1,2,3,4,8,12,16,32,48) и спросите о суммировании подмножеств до 63.)

Вы можете сформировать 1 + 2 либо используя 1 и 2, либо используя 1 + 2.

Вы можете сформировать 4 + 8, используя 4 и 8 или используя 4 + 8.

....

Вы можете сформировать 2 2n + 22n + 1 либо с помощью 2 2n и 2 2n + 1 или 22n + 22n + 1.

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

Смежные вопросы