Warianty bezpośrednich twierdzeń o produktach

11

Bezpośrednie twierdzenie o produkcie, nieformalnie, mówi, że obliczenie instancji funkcji f jest trudniejsze niż jednorazowe obliczenie f .kff

Typowe bezpośrednie twierdzenia o produktach (np. XOR Lemma Yao) patrzą na złożoność średnich przypadków i twierdzą (bardzo z grubsza), że nie może być obliczone przez obwody o wielkości s z prawdopodobieństwem większym niż p , wówczas k kopii f nie może być obliczone przez obwody o wielkości s < s z prawdopodobieństwem lepszym niż p k .fspkfs<spk

Szukam różnych rodzajów bezpośrednich twierdzeń o produktach (jeśli są znane). Konkretnie:

(1) Powiedzmy, że ustaliliśmy prawdopodobieństwo błędu i zamiast tego interesuje nas rozmiar obwodu potrzebnego do obliczenia k kopii f ? Czy istnieje wynik, który mówi, że jeśli f nie może być obliczone przez obwody o rozmiarze s z prawdopodobieństwem większym niż p , to k kopii f nie może być obliczone z prawdopodobieństwem lepszym niż p przy użyciu obwodu o rozmiarze mniejszym niż O ( k s ) ?pkffspkfpO(ks)

(2) Co wiadomo na temat złożoności najgorszego przypadku ? Na przykład, jeśli nie może być obliczone (z błędem 0) przez obwody o rozmiarze s , co możemy powiedzieć o złożoności obliczania k kopii f (z błędem 0)?fskf

Wszelkie referencje będą mile widziane.

użytkownik686
źródło

Odpowiedzi:

10

f0.99ps0.01psfkfss

f:{0,1}n{0,1}nn×nfn2nn3za pomocą algorytmu mnożenia macierzy. Dokładną dyskusję na ten temat można znaleźć w książce „Złożoność funkcji boolowskich” autorstwa Ingo Wegenera - patrz rozdział 10.2 tutaj: http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ .

Lub Meir
źródło
f2n
kfs+O(k)
2nkfkf
7

Aby uzupełnić odpowiedź Or, zbadano pytania na temat smaku (1) [ile zasobów potrzeba, aby dobrze sobie radzić z kopiami k], a odpowiadające im twierdzenia nazywane są „twierdzeniami o sumie bezpośredniej”. Podobnie jak w przypadku bezpośrednich twierdzeń o produktach, twierdzenia o bezpośrednich sumach mogą, ale nie muszą, w zależności od konfiguracji.

Dana Moshkovitz
źródło