Лас-Вегас против Монте-Карло сложности рандомизированного дерева решений

13

Фон:

Сложность дерева решений или сложность запросов - это простая модель вычислений, определяемая следующим образом. Пусть - булева функция. Детерминированная сложность запроса , обозначаемая , представляет собой минимальное количество битов входных данных которые должны быть прочитаны (в худшем случае) детерминированным алгоритмом, который вычисляет . Обратите внимание, что мера сложности - это количество битов ввода, которые читаются; все остальные вычисления бесплатны.f D ( f ) x { 0 , 1 } n f ( x )е:{0,1}N{0,1}еD(е)Икс{0,1}Nе(Икс)

Точно так же мы определяем сложность рандомизированного запроса в Лас-Вегасе для , обозначаемого , как минимальное количество входных битов, которые должны считываться в ожидании с помощью рандомизированного алгоритма с нулевой ошибкой, который вычисляет . Алгоритм с нулевой ошибкой всегда выводит правильный ответ, но количество прочитанных им входных битов зависит от внутренней случайности алгоритма. (Вот почему мы измеряем ожидаемое количество прочитанных входных битов.)R 0 ( f ) f ( x )ер0(е)е(Икс)

Мы определяем сложность рандомизированного запроса Монте-Карло для , обозначенную , как минимальное количество входных битов, которые должны быть прочитаны рандомизированным алгоритмом с ограниченной ошибкой, который вычисляет . Алгоритм с ограниченной ошибкой всегда выводит ответ в конце, но он должен быть корректным только с вероятностью более (скажем).R 2 ( е ) е ( х ) 2 / 3ер2(е)е(Икс)2/3


Вопрос

Что известно о вопросе

р0(е)знак равноΘ(р2(е)) ?

Известно, что

р0(е)знак равноΩ(р2(е))

потому что алгоритмы Монте-Карло, по крайней мере, такие же мощные, как алгоритмы Лас-Вегаса.

Недавно я узнал, что нет никакого известного разделения между этими двумя сложностями. Последняя ссылка, которую я могу найти для этого заявления, относится к 1998 году [1]:

[1] Николай К. Верещагин, Рандомизированные булевы деревья решений: несколько замечаний, Теоретическая информатика, том 207, выпуск 2, 6 ноября 1998 года, страницы 329-342, ISSN 0304-3975, http://dx.doi.org/ 10.1016 / S0304-3975 (98) 00071-1 .

Самая известная верхняя граница одного с точки зрения другого

р0(е)знак равноО(р2(е)2журналр2(е))

из-за [2]:

[2] Kulkarni, R. & Tal, A. (2013, ноябрь). Дробная Чувствительность Блоков. В электронном коллоквиуме по вычислительной сложности (ECCC) (Vol. 20, p. 168).

У меня есть два конкретных вопроса.

  1. [Справочный запрос]: есть ли более поздний документ (после 1998 года), в котором обсуждается эта проблема?
  2. Что еще более важно , есть ли функция-кандидат, которая, как предполагается, разделяет эти две сложности?

Добавлено в версии 2: добавлена ​​ссылка [2], выделен второй вопрос о существовании функции-кандидата.

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

Ответы:

7

Насколько я знаю, это все еще открыто. Самая недавняя статья, в которой упоминаются эти величины и некоторые границы, - Ааронсон и др .: Слабая четность (см. Http://arxiv.org/abs/1312.0036 ). Вы также можете увидеть главу 14 «Юкна: булевы функции» и обзор 1999 года (по-прежнему превосходит 1998!) Бермана и де Вольфа. Другая очень недавняя статья о рандомизированной сложности дерева решений - Magniez et al: http://arxiv.org/abs/1309.7565

Наконец, краткое резюме, которое я сделал для себя в прошлом месяце (без определений):

R 2 <= R 0 <= D <= п

D <= N0 * N1 <= С ^ 2 <= R 0 ^ 2

s <= bs <= C <= s * bs <= bs ^ 2 (новое: [Гилмер-Сакс-Шринивасан]: есть f st bs ^ 2 (f) = O (C (f)))

D <= N1 * BS <= BS ^ 3 <= (3R2) ^ 3

deg <= D <= bs * deg <= deg ^ 3 (новое: [Tal]: bs <= deg ^ 2)

D <= N1 * град

С <= шс * град ^ 2 <= 4 град ^

Гипотеза о чувствительности заключается в том, что s также полиномиально связан с другими параметрами.

domotorp
источник
Не могли бы вы указать конкретно, где эти документы ссылаются на вопрос об алгоритмах Лас-Вегас против Монте-Карло? Я пытался найти его в этих статьях, но не смог его найти.
Робин Котари
Прошу прощения, если я был неоднозначен, в этих работах явно не упоминается вопрос, только разные неравенства для разных параметров. Мое единственное доказательство открытости вопроса состоит в том, что если бы это было не так, это было бы упомянуто.
Домоторп
О, я понимаю, что вы имеете в виду. Я прочитал эти документы. Интересно, изучалась ли эта проблема специально совсем недавно? И мне также любопытно узнать, есть ли предположительная функция для разделения этих двух сложностей. (Или если люди считают, что они одинаковы.)
Робин Котари
Я знаю, что предполагается, что самое большое отделение от D - это дерево NAND для R0 и R2.
Домоторп
7

Этот вопрос был решен!

е

р0(е)знак равноΩ~(р2(е)2)

и даже

р0(е)знак равноΩ~(р1(е)2)

р1(е)

Оба разделения оптимальны с учетом логарифмических факторов!

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