Это продолжение этого вопроса на math.stackexchange.
Допустим, что непустое множество S ⊆ ℤ является самонесущим, если для каждого a ∈ S существуют различные элементы b, c ∈ S, такие что a = b + c. Для натуральных чисел n простые примеры включают идеал S = n ℤ или (для n > 3) целочисленный интервал [- n , n ].
Мы будем говорить, что S сильно самоподдерживающийся, если S не пересекается с −S: то есть, если a ∈ S, то - a ∉ S. Ни один из приведенных выше примеров не является полностью самоподдерживающимся, потому что они на самом деле замкнуты под отрицанием. Существуют конечные множества, которые сильно самодостаточны: например, множества {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15 , 23} и {−10, −8, −6, −2, 1, 3, 4, 5}.
Вопрос 1. Для положительного целого числа N > 0 существует ли алгоритм poly ( N ) -time [или polylog ( N ) -time], чтобы либо (i) создать сильно самоподдерживающийся набор, максимальное абсолютное значение которого равно N , либо (ii) ) определить, что такого набора не существует? [ Редактировать : как указано в самом старом ответе + мой комментарий к нему, такой набор всегда существует для N ≥ 10.]
Вопрос 2. При N > 0, вы можете построить сильно самонесущий набор с максимальным абсолютным значением N , который имеет наименьшее количество возможных элементов?
источник
Ответы:
Я полагаю, что для вопроса № 1) должен быть возможен линейный алгоритм времени (и если вы готовы иметь дело с другим представлением, алгоритмом времени O (1))
Для любого N> = 23 мы строим сильно самонесущее множество, которое содержит 1 и N.
Мы можем сделать это легко, если построим то же самое для N-1, а затем добавим N к результирующему набору.
Для базового случая 23 мы можем начать с вашего примера набора.
Чтобы уменьшить размер, мы должны использовать аналогичный подход:
Построить наборы, которые содержат
1, N and N-1.Мы используем эти ограниченные наборы и делаем эту конструкцию рекурсивно, чтобы уменьшить размер до O (logN) следующим образом:
Если N четное, для построения набора, содержащего 1, N и N-1, рекурсивно построить набор, содержащий 1, N / 2 и N / 2-1 (т. Е. Набор, соответствующий N / 2), и добавить N и N-1 в результирующий набор. Поскольку N-1 = N / 2 + N / 2-1 и N = 1 + N-1, это допустимый набор.
Если N нечетно, построить набор для N-1 и N для результирующего набора.
Для базовых случаев мы можем начать с {−22, −20, −18, −16, −14, −12, −10, −10, −2, 1, 3, 7, 8, 15, 23,24} для N = 24. Для 24 <N <= 47 мы можем использовать описанный выше алгоритм линейного времени и строить на основе набора для N = 24. Для N> = 48 мы переключаемся на уменьшение наполовину.
Фактически, для составного N мы можем уменьшить размер до размера, необходимого для одного из небольших простых чисел, которое делит N: найти множество для малого простого числа и просто умножить все числа на подходящий коэффициент.
Может быть интересно доказать некоторые нижние оценки в случае, когда N простое.
источник
Для N ≥ 10 можно построить сильно самонесущий набор размером не более одиннадцати, как показано ниже:
Более короткий пример, представленный в исходном вопросе, соответствует случаю N = 10. Это близко к тому, чтобы быть оптимальным, поскольку любой сильно самоподдерживающийся набор должен иметь количество элементов не менее восьми .
Таким образом, проблема разрешима за время O (log (N)) [занятое в мирских арифметических операциях над N], что дает набор мощностей от восьми до одиннадцати.
Конструкция для этого ответа была впервые представлена для вопроса math.stackoverflow , который также дает интуицию для построения. Можем ли мы получить еще меньшие конструкции, например, сопоставляя нижнюю границу из восьми для каждого N> 9? Как насчет случаев N ∈ {8,9}?
источник