Фон:
Сложность дерева решений или сложность запросов - это простая модель вычислений, определяемая следующим образом. Пусть - булева функция. Детерминированная сложность запроса , обозначаемая , представляет собой минимальное количество битов входных данных которые должны быть прочитаны (в худшем случае) детерминированным алгоритмом, который вычисляет . Обратите внимание, что мера сложности - это количество битов ввода, которые читаются; все остальные вычисления бесплатны.f D ( f ) x ∈ { 0 , 1 } n f ( x )
Точно так же мы определяем сложность рандомизированного запроса в Лас-Вегасе для , обозначаемого , как минимальное количество входных битов, которые должны считываться в ожидании с помощью рандомизированного алгоритма с нулевой ошибкой, который вычисляет . Алгоритм с нулевой ошибкой всегда выводит правильный ответ, но количество прочитанных им входных битов зависит от внутренней случайности алгоритма. (Вот почему мы измеряем ожидаемое количество прочитанных входных битов.)R 0 ( f ) f ( x )
Мы определяем сложность рандомизированного запроса Монте-Карло для , обозначенную , как минимальное количество входных битов, которые должны быть прочитаны рандомизированным алгоритмом с ограниченной ошибкой, который вычисляет . Алгоритм с ограниченной ошибкой всегда выводит ответ в конце, но он должен быть корректным только с вероятностью более (скажем).R 2 ( е ) е ( х ) 2 / 3
Вопрос
Что известно о вопросе
?
Известно, что
потому что алгоритмы Монте-Карло, по крайней мере, такие же мощные, как алгоритмы Лас-Вегаса.
Недавно я узнал, что нет никакого известного разделения между этими двумя сложностями. Последняя ссылка, которую я могу найти для этого заявления, относится к 1998 году [1]:
[1] Николай К. Верещагин, Рандомизированные булевы деревья решений: несколько замечаний, Теоретическая информатика, том 207, выпуск 2, 6 ноября 1998 года, страницы 329-342, ISSN 0304-3975, http://dx.doi.org/ 10.1016 / S0304-3975 (98) 00071-1 .
Самая известная верхняя граница одного с точки зрения другого
из-за [2]:
[2] Kulkarni, R. & Tal, A. (2013, ноябрь). Дробная Чувствительность Блоков. В электронном коллоквиуме по вычислительной сложности (ECCC) (Vol. 20, p. 168).
У меня есть два конкретных вопроса.
- [Справочный запрос]: есть ли более поздний документ (после 1998 года), в котором обсуждается эта проблема?
- Что еще более важно , есть ли функция-кандидат, которая, как предполагается, разделяет эти две сложности?
Добавлено в версии 2: добавлена ссылка [2], выделен второй вопрос о существовании функции-кандидата.
Этот вопрос был решен!
и даже
Оба разделения оптимальны с учетом логарифмических факторов!
источник