Обнаружение целочисленных отношений для Подмножества Сумм или АЭС?

Есть ли способ закодировать экземпляр суммы подмножества или проблему разбиения числа так, чтобы (небольшое) решение целочисленного отношения дало ответ? Если не точно, то в каком-то вероятностном смысле?

Я знаю, что LLL (и, возможно, PSLQ) использовались с умеренным успехом в решении задач Subset Sum в области «низкой плотности», где диапазон выбранных чисел больше , но эти методы плохо масштабируются для случаи большего размера и потерпеть неудачу в «высокой плотности» области, когда диапазон чисел , выбранных намного меньше , чем . Здесь низкая плотность и высокая плотность относится к числу решений. Область с низкой плотностью относится к небольшому количеству или отсутствию существующих решений, тогда как область с высокой плотностью относится к области со многими решениями. $2^N$ $2^N$

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

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

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

cc.complexity-theory np-hardness approximation-algorithms reductions subset-sum user834
источник

Я не получил никаких ответов, поэтому я написал кроссворд на mathoverflow: mathoverflow.net/questions/38063/…

user834

Это очень интересный вопрос, я тоже жду ответов. Вы в основном просите сокращение полиномиального времени (возможно, случайное) от суммы подмножества или NPP до целочисленного отношения. Как насчет этого, если

является целью вашей проблемы суммы подмножеств, а

является множеством натуральных чисел, причем

решение, удовлетворяющее

. Это в точности линейная комбинация с действительными коэффициентами, равными 1. Если для каждого

вас есть, что

t = 0

$t=0$

S

$S$

S^{'}

$S'$

0 = \sum_{a \in S^{'}} a

$0=\sum_{a\in S'} a$

a_{i} \in S

$a_i \in S$

всегда есть решение, и связь с целочисленными значениями также даст вам решение.

\sum_{i} a_{i} < 2^{n} - 1

$\sum_i a_i < 2^n-1$

Маркос Вильягра

@Marcos Вильягра: Ваш комментарий немного трудно разобрать ... Можно встроить эту проблему как проблему разбиения подмножество сумма / количество в решетке (см здесь для обзора), вопрос найти способ ограничить коэффициенты к желаемый набор (скажем, 0,1 или -1,1). LLL найдет целочисленное отношение, даже небольшое, но только одно 2 или 3 в качестве коэффициента сделает его недействительным как ответ на подмножество сумма / число.

user834

$m=O(\log n)$ $\Omega(2^{m})$ $m=\omega(\log n)$ $m=o(n)$

Тем не менее, Flaxman и Przydatek предоставляют алгоритм, который решает проблемы подмножеств средней плотности в ожидаемое полиномиальное время.

Проверьте эту ссылку:

Flaxman и Przydatek, Решение проблем подмножеств средней плотности в ожидаемое полиномиальное время

Мухаммед Аль-Туркистани
источник

Этот результат предназначен только для выбора чисел в экземпляре Subset Sum, которые значительно ниже, чем я хочу. Они выбирают диапазон чисел порядка log (n) ^ 2, тогда как меня интересует диапазон чисел порядка 2 ^ n. Есть хорошо известные алгоритмы для решения Subset Sum, когда диапазон чисел ограничен настолько малым, и похоже, что они только немного расширили этот диапазон, и это здорово, это просто не то, что я искал. Однако, спасибо.

user834

Обнаружение целочисленных отношений для Подмножества Сумм или АЭС?

Ответы: