Что известно о временной сложности следующей задачи, которую мы называем 3-MUL?
Для заданного множества из целых чисел существуют ли такие элементы , что ?
Эта проблема похожа на задачу 3-СУММ, которая спрашивает, существуют ли три элемента такие что (или эквивалентно ). Предполагается, что 3-СУММ требует приблизительно квадратичного времени по . Есть ли подобная гипотеза для 3-MUL? В частности, известно, что 3-MUL - это 3-SUM?
Обратите внимание, что временная сложность должна применяться в «разумной» модели вычислений. Например, мы могли бы уменьшить значение с 3-СУММ на множестве до 3-МУЛ на множестве , где . Тогда решение 3-MUL, , существует тогда и только тогда, когда . Однако это экспоненциальное увеличение чисел очень плохо масштабируется с различными моделями, такими как модель ОЗУ, например.
источник
Ответы:
Ваше сокращение с3 СУМ до 3 МУЛ работает с незначительной стандартной модификацией. Предположим, что ваши исходные целые числа были в { 1,…,M }. После преобразования x→2x новые целые числа находятся в { 2,…,2M }. Мы будем уменьшать ассортимент.
Рассмотрим любую тройку целых чисел в новом множестве S ′ . Число простых делителей любого ненулевого б - с является < 2 М . Количество таких троек n 3 . Следовательно, число простых чисел q, которые делят хотя бы одно из ненулевых чисел a b - c , не больше 2 M n 3 .a,b,c S′ ab−c <2M n3 q ab−c 2Mn3
Пусть - множество первых 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 в SP 2M⋅n4 O(Mn4logMn) p∈P p ab−c a∈S′ p 3 ab=c С высокой вероятностью это будет правильным для исходногоэкземпляра 3 SUM. Мы сократили диапазон чисел до { 0 , … , O ( M n 4 log M n ) }.S′ 3 0,…,O(Mn4logMn)
(Это стандартное уменьшение размера. Возможно, вам удастся добиться большего, если учесть тот факт, что всегда являются разностями двух степеней 2 ).ab−c 2
источник
источник