Bezpośrednie twierdzenie o produkcie, nieformalnie, mówi, że obliczenie instancji funkcji f jest trudniejsze niż jednorazowe obliczenie 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 .
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 ) ?
(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)?
Wszelkie referencje będą mile widziane.
źródło
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.
źródło