Как вы, вероятно, знаете, проблема 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 Я знаю, это звучит как вопрос о домашнем задании, но, пожалуйста, поверьте мне, что это не так. Я пытаюсь научить себя определенным аспектам теории СС, и именно здесь мои мысли приняли меня.
mathoverflow.com? – JonH
Рассмотрим '((2 2 2 2 2 2 2 2 2 2) 10)'. Здесь есть 252 комбинации из 5 2, которые вы можете выбрать, чтобы получить 10. Если вы считаете ответы с одинаковыми номерами, но разные индексы одинаковы, то в этом случае есть только одно решение. Не могли бы вы сосчитать выше 252 решения или всего 1? –
1, я должен был упомянуть, что меня интересуют уникальные решения. – Mike