Batas bawah yang lebih baik daripada 3n untuk fungsi non-boolean?

Batas bawah Blum adalah sirkuit batas bawah paling dikenal atas dasar lengkap untuk fungsi eksplisit f : { 0 , 1 } n → { 0 , 1 } , lih. Jawaban Jukna untuk pertanyaan ini untuk hasil terkait.$3n-o(n)$$f : \{0,1\}^n \to \{0,1\}$

Apa batas bawah paling dikenal jika rentang adalah { 0 , 1 } m ? Secara khusus, apakah kita mendapatkan sesuatu yang lebih baik untuk m = n , atau untuk m = 2 ?$f$$\{0,1\}^m$$m = n$$m = 2$

Menurut makalah A Bawah pada Ukuran Sirkuit lebih dari Fungsi Linear Boolean$5n − o(n)$$U_2$ oleh Kulikov, Melanich, dan Mihajlin, ketika tidak ada batas bawah yang diketahui lebih baik dari . Ini juga menguraikan metode untuk mendapatkan fungsi yang memegang batas bawah , ketika , berdasarkan hasil Lamagne dan Savage.$m=o(n)$$3n - o(n)$$4n - o(n)$$m=n$

di sini adalah hasil baru ini dikatakan 1 ^st di ~ 3 dekade dan beberapa komentar singkat

• Batas bawah yang lebih baik dari 3n untuk kompleksitas sirkuit fungsi eksplisit / Find, Golovnev, Hirsch, Kulikov

  Kami mempertimbangkan sirkuit Boolean atas dasar biner penuh. Kami membuktikan lebih rendah terikat pada ukuran sirkuit seperti itu untuk predikat yang ditentukan secara eksplisit, yaitu afine disperser untuk dimensi sublinear. Ini meningkatkan batas dari Norbert Blum (1984).$(3+\frac{1}{86})n−o(n)$$3n−o(n)$

• Lebih Baik Sirkuit Bawah Batas untuk Fungsi Eksplisit / Ilya Razenshteyn, blog mahasiswa MIT CSAIL