Компромисс между временем и сложностью запроса

18

Работать напрямую со сложностью времени или нижними границами схемы страшно. Следовательно, мы разрабатываем такие инструменты, как сложность запросов (или сложность дерева решений), чтобы справиться с нижними границами. Поскольку каждый запрос занимает по крайней мере один блок-шаг, а вычисления между запросами считаются бесплатными, сложность времени по меньшей мере столь же высока, как и сложность запроса. Однако можем ли мы что-нибудь сказать об увольнениях?

Мне интересно работать в классической или квантовой литературе, но я привожу примеры из КК, так как я более знаком.

В некоторых известных алгоритмах, таких как поиск Гровера и нахождение периода Шора, сложность времени находится в пределах логарифмических факторов сложности запроса. Для других, таких как проблема скрытой подгруппы, мы имеем сложность полиномиального запроса , но алгоритмы полиномиального времени не известны.

Поскольку существует потенциальный разрыв между временем и сложностью запроса, не ясно, что алгоритм оптимальной сложности времени должен иметь ту же сложность запроса, что и алгоритм оптимальной сложности запроса.

Есть ли примеры компромиссов между временем и сложностью запроса?

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

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

Артем Казнатчеев
источник
Вы хотите естественную проблему или искусственная проблема тоже хорошо?
Робин Котари
2
Естественные проблемы предпочтительнее, но искусственные проблемы лучше, чем отсутствие ответа.
Артем Казнатчеев

Ответы:

9

Вот попытка создания искусственной функции со следующим свойством:

  • Проблема может быть решена с помощью запросов, но требует времени exp ( n ) .O(logn)exp(n)
  • Проблема может быть решена с времени, но это требует O ( N ) запросовO(n)O(n)

Пусть размер ввода будет . Пусть первые log n битов (назовем эту строку x) кодируют входные данные для задачи, завершенной для EEXP. Следующие n битов (давайте назовем эту строку y) обладают свойством того, что все они равны нулю тогда и только тогда, когда x является НЕТ экземпляром задачи, полной EEXP.n+lognlognn

На словах первого биты кодируют нелегкую задачу, а следующий п бит дать вам подсказку о решении этой проблемы. Однако, чтобы найти решение, взглянув на n- битную строку, вы сделаете Ω ( n ) запросов.lognnnΩ(n)

Таким образом, эта проблема может быть решена либо чтением только первых битов n и затрачиванием времени exp (n), либо считыванием n битов и использованием только линейного времени.lognn

Эта же функция выполняется для сложности квантовых запросов. При необходимости вставляйте знаки квадратного корня.

Робин Котари
источник
7

Более экстремальная версия примера Робина:

Пусть входной размер равен , а первые n - 1 бит (назовите эту строку x ) кодируют машину Тьюринга T x . Исправьте некоторую функцию f ( n ) . Пусть последний бит строки равен 1, если машина Тьюринга T x останавливается менее чем за f ( n ) шагов. Задача состоит в том, чтобы определить, останавливается ли T x менее чем за f ( n ) шагов и четность x четна.nn1xTxf(n)1Txf(n)Txf(n)x

Таким образом, с помощью запросов проблема может быть решена за время O ( f ( n ) ) , а с помощью n запросов проблема может быть решена за время O ( n ) .n1O(f(n))nO(n)

Джо Фитцсимонс
источник
Вы, вероятно, имели в виду, что последний бит будет таким, что четность x будет даже тогда, когда машина Тьюринга остановится во времени (в противном случае вопрос требует только одного запроса;)). Это хорошо и может быть изменено, чтобы обеспечить любое различие между временем и запросом. Рассмотрим любую функцию и g ( n ) < n , затем пусть первые g ( n ) битов x являются описанием токарного станка. Пусть другой n - g ( n ) из xg(n)=ω(1)g(n)<ng(n)xng(n)xбиты должны быть такими, чтобы четность была четной, если T x останавливается менее чем за f ( n ) > n шагов. Тогда мы имеем g ( n ) против n запросов за счет Θ ( f ( n ) ) против n во времени. xTxf(n)>ng(n)nΘ(f(n))n
Артем Казнатчеев
Не обращайте внимания на первое предложение моего предыдущего комментария.
Артем Казнатчеев
7

Мне нравится ответ Робина Котари и модификация Джо Фицсимона. В очевидном расширении своих ответов они могут достичь любого отношения разделения (кроме константы и константы) между меньшей и большей сложностью запроса и большей и меньшей временной сложностью. Однако не существует очевидного способа сделать их функции не частичными. Я хочу указать на естественную проблему, когда у нас есть разделение, и показать, что большие разделения сложнее для полных функций.


Естественная проблема

nΘ(n)O(n)O(nlogn)

Всего функций сложнее разделить?

Мне кажется, что сложнее найти полные функции с доказуемым разделением. Чтобы показать, что случай общих и частичных функций различен, я приведу аргумент о наибольшем разделении между сложностями запросов оптимальных по запросу и оптимальных по времени алгоритмов для полной функции.

Используя нижнюю границу [1] Саймона, мы можем видеть, что если функция зависит от mΩ(logm)mnnmm0

, то для полной функции, учитывая оптимальный по запросу алгоритм со сложностью ( q 1 ( n ) , t 1 ( n ) ) , существует оптимальный по времени алгоритм со сложностью ( q 2 ( n ) , t 2(query complexity,time complexity)(q1(n),t1(n))(q2(n),t2(n))q2(n)f(q1(n))f(n)=O(2n)

[1] Х. У. Саймон, «Жесткая Z (loglogn) привязанная ко времени параллельная память RAM для вычисления невырожденных булевых функций», в: Symp. Основы теории вычислений. Конспект лекций по информатике. 158, Springer, Berlin, 1983, pp. 439–444.

Артем Казнатчеев
источник