Вопросы с тегом «query-complexity»

22
Естественные, непроверяемые свойства графа

Во время тестирования свойств графов, алгоритм запрашивает целевой график на наличие или отсутствие ребер и потребностей , чтобы определить , либо имеет ли целевые определенное свойство или εε\epsilon -far от того , свойства. (Алгоритм можно попросить преуспеть с 1-сторонней или 2-сторонней...

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

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

18
Модели вычислений строго между классическими и квантовыми с точки зрения сложности запросов

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

18
Восстановление дерева по запросам разделителей

Предположим, что TTT - дерево постоянной степени, структура которого мы не знаем. Проблема состоит в том, чтобы вывести дерево , задавая запросы в форме: «Находится ли узел на пути от узла к узлу ?». Предположим, что на каждый запрос оракул может ответить в постоянное время. Мы знаем значение ,...

17
Использование дополнительной силы метода отрицательного противника

Метод отрицательного противника ( ) - это SDP, характеризующий сложность квантового запроса. Это обобщение широко используемого метода противника ( A D V ), и оно преодолевает два барьера, мешающих противнику:A D V±ADВ±ADV^\pmA D VADВADV Барьер тестирования свойств: если все 0-экземпляры находятся...

16
Алгоритм оптимизации деревьев решений

Фон Бинарное дерево решений представляет собой корневое дерево , где каждый внутренний узел (и корень) помечен индекс J ∈ { 1 , . , , , n } , так что путь от корня к листу не повторяет индекс, листья помечаются выходами в { A , B } , а каждое ребро помечается 0 для левого потомка и 1 для правого...

15
Информационная сложность алгоритмов запросов?

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

13
Существуют ли свойства распределения, которые «максимально» сложно проверить?

Алгоритм тестирования распределения для свойства распределения P (которое является лишь некоторым подмножеством всех распределений по [n]) разрешает доступ к выборкам в соответствии с некоторым распределением D и должен решить (whp), если или ( здесь, как правило, расстояние). Наиболее...

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

Фон: Сложность дерева решений или сложность запросов - это простая модель вычислений, определяемая следующим образом. Пусть - булева функция. Детерминированная сложность запроса , обозначаемая , представляет собой минимальное количество битов входных данных которые должны быть прочитаны (в худшем...

12
Могут ли квантовые алгоритмы с экспоненциальным ускорением быть переизобретены с использованием программ span?

Известно, что нижняя граница общего противника характеризует сложность квантового запроса благодаря прорывной работе Reichardt et al. Та же самая линия работы также устанавливает связи со структурой программы span для разработки квантовых алгоритмов. Многие интересные квантовые алгоритмы, включая...

11
Нижние границы для обучения в запросе членства и модели контрпримеров

Дана Англюин ( 1987 ; pdf ) определяет модель обучения с помощью запросов на членство и теоретических запросов (контрпримеры к предложенной функции). Она показывает, что регулярный язык, представленный минимальным DFA из состояний, может быть изучен за полиномиальное время (где предложенные функции...

10
Программы Span, размер свидетеля и сложность сертификата

Span-программа - это линейно-алгебраический способ задания булевой функции, представленный здесь . Недавно эта модель использовалась, чтобы показать, что метод отрицательного противника обеспечивает точную характеристику (по крайней мере, до ) сложности квантовых...

10
Ограничение разрыва между квантовой и детерминированной сложностью запросов

Хотя экспоненциальное разделение между сложностью квантового запроса с ограниченной ошибкой ( Q ( f)Q(f)Q(f) ) и сложностью детерминированного запроса ( Д ( ф)D(f)D(f) ) или сложностью рандомизированного запроса с ограниченной ошибкой ( R ( f)R(f)R(f) ) известно, они применяются только к...

9
Нижние оценки пороговой функции

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