Varian teorema produk langsung

Teorema produk langsung, secara informal, mengatakan bahwa komputasi contoh fungsi f lebih sulit daripada komputasi f satu kali.$k$$f$$f$

Teorema produk langsung khas (misalnya, XOR Lemma Yao) melihat kompleksitas kasus rata-rata , dan berdebat (sangat kasar) bahwa tidak dapat dihitung oleh sirkuit ukuran s dengan probabilitas lebih baik dari p , maka k salinan f tidak dapat dihitung oleh sirkuit ukuran s ′ < s dengan probabilitas lebih baik dari p k .$f$$s$$p$$k$$f$$s' < s$$p^k$

Saya mencari berbagai jenis teorema produk langsung (jika diketahui). Secara khusus:

(1) Katakanlah kita memperbaiki probabilitas kesalahan dan sebaliknya tertarik pada ukuran sirkuit yang diperlukan untuk menghitung k salinan f ? Apakah ada hasil yang mengatakan bahwa jika f tidak dapat dihitung oleh sirkuit ukuran s dengan probabilitas lebih baik dari p , maka k salinan f tidak dapat dihitung dengan probabilitas lebih baik daripada p menggunakan sirkuit ukuran kurang dari O ( k ⋅ s ) ?$p$$k$$f$$f$$s$$p$$k$$f$$p$$O(k \cdot s)$

(2) Apa yang diketahui sehubungan dengan kompleksitas kasus terburuk ? Misalnya, jika tidak dapat dihitung (dengan 0 kesalahan) oleh sirkuit ukuran s , apa yang bisa kita katakan tentang kompleksitas komputasi k salinan f (dengan 0 kesalahan)?$f$$s$$k$$f$

Referensi apa pun akan dihargai.

$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$menggunakan algoritma penggandaan matriks. Anda dapat menemukan diskusi menyeluruh tentang subjek ini dalam buku "Kompleksitas Fungsi Boolean" oleh Ingo Wegener - lihat Bab 10.2 di sini: http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/ .

Hanya untuk melengkapi jawaban Or, pertanyaan tentang rasa (1) [berapa banyak sumber daya yang diperlukan untuk melakukannya dengan baik pada k copy] dipelajari, dan teorema yang sesuai disebut "teorema jumlah langsung". Seperti halnya teorema produk langsung, teorema jumlah langsung dapat atau tidak dapat ditahan, tergantung pada pengaturannya.