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

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

Мера сложности, связывающая программы span с квантовой сложностью запроса, - это размер свидетеля. Эта мера кажется довольно похожей на сложность сертификата. Есть ли известные связи между этими двумя мерами? Как насчет измерения размера (числа входных векторов) для программ диапазона и других мер, таких как детерминистическая и рандомизированная сложность запросов? Каковы наиболее известные классические алгоритмы для оценки пролетных программ?

РЕДАКТИРОВАТЬ (после ответа Мартина Шварца):

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

cc.complexity-theory reference-request quantum-computing query-complexity Артем Казнатчеев
источник

Ответы:

Минимальный размер свидетеля для всех свидетелей программы span для данной функции равен обобщенной границе противника, как показано, например, в теореме 1.7 здесь . Кроме того,~~обобщаются~~граница противника - это лишь полуопределенное ослабление сложности сертификата, см., например, слайд 40 в руководстве Рейхардта . Отношение к детерминированной и рандомизированной сложности запросов также обсуждается в этих учебных слайдах.

Мартин Шварц
источник

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

f

$f$

C (f) = 3

$C(f) = 3$

A D V^{\pm} (f) = 2 + 3 \sqrt{5} / 5 > 3

$ADV^{\pm}(f) = 2 + 3\sqrt{5}/5 > 3$

Артем Казнатчеев

Хорошо я согласен. Таким образом, аргумент в пользу релаксации, похоже, действительно применим только к переходу от C (f) к ADV (f). В любом случае, я думаю, что слайд 40, на который я ссылался выше, хорошо суммирует шаги обобщения, взятые из C (f) посредством релаксации в ADV (f), а затем через другое обобщение в ADV ± (f), которое является связью между C (f). ) и ADV ± (f), о которых вы спрашивали.

Мартин Шварц

Спасибо за ответ. Этот тип соединения проходит непосредственно через сложность запроса и относится к предыдущему вопросу , но я думаю, что я пытаюсь найти более прямые соединения через программы span. В частности, я пытаюсь получить более полное представление о самих программах, не используя мои знания о сложности квантовых запросов. Я отредактирую свой вопрос, чтобы сделать это более ясным и посмотреть, будет ли он генерировать какие-либо дополнительные сведения о программах span.

Артем Казнатчеев