Warianty bezpośrednich twierdzeń o produktach

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

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 .$f$$s$$p$$k$$f$$s' < s$$p^k$

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 ) ?$p$$k$$f$$f$$s$$p$$k$$f$$p$$O(k \cdot s)$

(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)?$f$$s$$k$$f$

Wszelkie referencje będą mile widziane.

$f$$0.99 * p$$s$$0.01 * p$$s$$f$$k$$f$$s$$s$

$f : \{0,1\}^n \to \{0,1\}^n$$n \times n$$f$$n^2$$n$$n^3$za 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/ .

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.