Мультипликативная версия 3-СУММ

22

Что известно о временной сложности следующей задачи, которую мы называем 3-MUL?

Для заданного множества S из n целых чисел существуют ли такие элементы a,b,cS , что ab=c ?

Эта проблема похожа на задачу 3-СУММ, которая спрашивает, существуют ли три элемента a,b,cS такие что a+b+c=0 (или эквивалентно a+b=c ). Предполагается, что 3-СУММ требует приблизительно квадратичного времени по n . Есть ли подобная гипотеза для 3-MUL? В частности, известно, что 3-MUL - это 3-SUM?

Обратите внимание, что временная сложность должна применяться в «разумной» модели вычислений. Например, мы могли бы уменьшить значение с 3-СУММ на множестве S до 3-МУЛ на множестве S , где S={2xxS} . Тогда решение 3-MUL, 2a2b=2c , существует тогда и только тогда, когда a+b=c . Однако это экспоненциальное увеличение чисел очень плохо масштабируется с различными моделями, такими как модель ОЗУ, например.

Маркус Ялсениус
источник
Ваше сокращение показывает, что 3-MULT сложнее 3-SUM, если входные числа могут быть выражены с использованием экспоненциальной (иначе говоря, научной) записи.
Уоррен Шуди
4
Любой алгоритм для 3-SUM, основанный исключительно на том факте, что сложение является группой, может быть преобразован в алгоритм для 3-MULT и наоборот. Поэтому любой алгоритм, разделяющий их, должен был бы делать что-то необычное с числами.
Уоррен Шуди
1
чтобы быть ужасно педантичным, нам может понадобиться только полугруппа.
Суреш Венкат

Ответы:

11

Ваше сокращение с 3 СУМ до 3 МУЛ работает с незначительной стандартной модификацией. Предположим, что ваши исходные целые числа были в { 1,,M }. После преобразования x2x новые целые числа находятся в { 2,,2M }. Мы будем уменьшать ассортимент.

Рассмотрим любую тройку целых чисел в новом множестве S . Число простых делителей любого ненулевого б - с является < 2 М . Количество таких троек n 3 . Следовательно, число простых чисел q, которые делят хотя бы одно из ненулевых чисел a b - c , не больше 2 M n 3 .a,b,cSabc<2Mn3qabc2Mn3

Пусть - множество первых 2 M n 4 простых чисел. Наибольшее такое простое число имеет размер не более O ( M n 4 log M n ) . Выберите случайный простой р P . С большой вероятностью p не будет делить ни одного из ненулевых a b - c , поэтому мы можем представить каждое a S его вычетом, mod p , и если 3 MUL найдет некоторое a b = c в SP2Mn4O(Mn4logMn)pPpabcaSp3ab=c С высокой вероятностью это будет правильным для исходногоэкземпляра 3 SUM. Мы сократили диапазон чисел до { 0 , , O ( M n 4 log M n ) }.S30,,O(Mn4logMn)

(Это стандартное уменьшение размера. Возможно, вам удастся добиться большего, если учесть тот факт, что всегда являются разностями двух степеней 2 ).abc2

Virgi
источник
1
ab=c(mod()p)abc
1
Да, как есть, это сокращение до 3MUL мод р. Хорошая точка зрения.
Дева
Это очень интересный подход. Тем не менее, мы особенно заинтересованы в детерминированном сокращении с 3-СУММ до 3-МУЛ. Возможно ли было бы дерандомизировать технику уменьшения размера?
Маркус Ялсениус
3

S={2x/M|xS}M=maxSminS

Уоррен Шуди
источник
К сожалению, случайного шума недостаточно для исправления ошибки округления. Однако эти идеи кажутся многообещающими для сокращения другого способа показать, что 3-MULT не сложнее, чем 3-SUM, поскольку, например, . (x+1)+y=x+y+1
Уоррен Шуди
1
Уравнение кажется неправильным (попробуйте x и y = 2.1). Не могли бы вы уточнить, что вы имели в виду?
Рафаэль