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

10

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

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

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

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

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

Ответы:

5

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

Мартин Шварц
источник
Я могу видеть, что (положительный) метод злоумышленника - это ослабление SDP сложности сертификата, но я не слежу за тем, как общий (отрицательный) метод злоумышленника является ослаблением сложности сертификата. В качестве контрпримера, похоже, здесь (стр. 25) дается функция с и , C ( f ) = 3 A D V ± ( f ) = 2 + 3 fC(f)=3ADV±(f)=2+35/5>3
Артем Казнатчеев
Хорошо я согласен. Таким образом, аргумент в пользу релаксации, похоже, действительно применим только к переходу от C (f) к ADV (f). В любом случае, я думаю, что слайд 40, на который я ссылался выше, хорошо суммирует шаги обобщения, взятые из C (f) посредством релаксации в ADV (f), а затем через другое обобщение в ADV ± (f), которое является связью между C (f). ) и ADV ± (f), о которых вы спрашивали.
Мартин Шварц
Спасибо за ответ. Этот тип соединения проходит непосредственно через сложность запроса и относится к предыдущему вопросу , но я думаю, что я пытаюсь найти более прямые соединения через программы span. В частности, я пытаюсь получить более полное представление о самих программах, не используя мои знания о сложности квантовых запросов. Я отредактирую свой вопрос, чтобы сделать это более ясным и посмотреть, будет ли он генерировать какие-либо дополнительные сведения о программах span.
Артем Казнатчеев