Programy rozpiętości, rozmiar świadka i złożoność certyfikatu

Program zakresu to liniowo-algebraiczny sposób określania wprowadzonej tutaj funkcji boolowskiej . Ostatnio model ten został użyty do wykazania, że metoda negatywnego przeciwnika zapewnia ścisłą charakterystykę (przynajmniej do ) złożoności kwantowych zapytań. $\log n/ \log \log n$

Miarą złożoności łączącą programy zakresu z kwantową złożonością zapytań jest wielkość świadka. Ta miara wydaje się raczej podobna do złożoności certyfikatu. Czy istnieją znane powiązania między tymi dwoma środkami? Co z miarą wielkości (liczby wektorów wejściowych) dla programów zakresu i innymi miarami, takimi jak deterministyczna i losowa złożoność zapytań? Jakie są najbardziej znane klasyczne algorytmy do oceny programów zakresu?

EDYCJA (po odpowiedzi Martina Schwarza):

Szczególnie interesujące są połączenia koncepcyjne, które przechodzą bezpośrednio przez programy zakresowe, w przeciwieństwie do zgodności między wielkością świadka a złożonością kwantowych zapytań. Czy istnieją klasyczne wyniki, które dostarczają intuicji na temat programów rozpiętości / wielkości świadka i ich związku z deterministyczną i losową złożonością zapytań?

cc.complexity-theory reference-request quantum-computing query-complexity Artem Kaznatcheev
źródło

Odpowiedzi:

Minimalna wielkość świadka dla wszystkich świadków programu zakresu dla danej funkcji jest równa uogólnionemu ograniczeniu przeciwnika, jak pokazano np. W Twierdzeniu 1.7 tutaj . Ponadto,~~uogólnione~~granica przeciwnika to tylko półokreślone złagodzenie złożoności certyfikatu, patrz np. slajd 40 w samouczku Reichardta . Związek z deterministyczną i losową złożonością zapytań omówiono również na tych slajdach z samouczkami.

Martin Schwarz
źródło

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$

Ok zgadzam się. Tak więc argument relaksacyjny wydaje się dotyczyć tylko kroku od C (f) do ADV (f). W każdym razie, myślę, że slajd 40, o którym mówiłem powyżej, ładnie podsumowuje kroki uogólnienia podjęte z C (f) przez relaksację do ADV (f), a następnie poprzez kolejne uogólnienie do ADV ± (f), czyli połączenie między C (f ) i ADV ± (f), o które pytałeś.

Martin Schwarz

Dziękuję za odpowiedź. Ten rodzaj połączenia przechodzi bezpośrednio przez złożoność zapytań i odnosi się do poprzedniego pytania , ale myślę, że staram się szukać bardziej bezpośrednich połączeń za pomocą programów span. W szczególności staram się uzyskać lepszy wgląd w same programy zakresowe bez korzystania z mojej wiedzy na temat złożoności kwantowych zapytań. Przeredaguję moje pytanie, aby było bardziej jasne i zobaczyć, czy generuje to więcej wglądu w programy zakresu.

Artem Kaznatcheev