Mengapa batas bawah untuk Sirkuit boolean tidak menyiratkan sirkuit aritmatika batas bawah

Pertanyaan saya adalah mengapa batas bawah untuk kedalaman 3 sirkuit Boolean dengan gerbang "dan" dan "xor" untuk determinan tidak menyiratkan batas bawah yang sama untuk sirkuit aritmatika di atas $\mathbb{Z}$ ?

Apa yang salah dengan argumen berikut: Misalkan $C$ menjadi rangkaian penentu penghitungan aritmatika maka dengan mengambil semua variabel mod 2 kita akan mendapatkan penentu penghitung penghitung sirkuit Boolean.

Untuk rangkaian aritmatika lebih dari $\mathbb{Z}$ argumen Anda tepat. Argumen yang sama berfungsi untuk rangkaian aritmatika di atas $\mathbb{Q}$ yang tidak menggunakan pecahan $a/b$ mana $b$ adalah genap.

Namun, argumen tidak lagi berfungsi jika Anda berbicara tentang sirkuit aritmatika di atas cincin lain, seperti: sirkuit aritmatika umum di atas (yaitu tanpa batasan di atas), R , bidang bilangan aljabar, C , atau bidang hingga F q dengan q ≠ 2 .$\mathbb{Q}$$\mathbb{R}$$\mathbb{C}$$\mathbb{F}_{q}$$q \neq 2$

(Ini pada dasarnya alasan yang sama bahwa dalam geometri aljabar sering dianggap sebagai "karakteristik campuran," daripada karakteristik nol.)$\mathbb{Z}$

Namun, kedalaman 3 Boolean menurunkan batas untuk sirkuit dengan {AND, OR, NOT} kurang mudah berhubungan dengan menurunkan batas untuk sirkuit aritmatika lebih . (Ya, {DAN, XOR} adalah basis yang lengkap, tetapi biasanya kedalaman 3 sirkuit di atas {DAN, ATAU, TIDAK} Anda menganggap BUKAN gerbang gratis, sedangkan menerapkan BUKAN dengan XOR Anda kemudian menggunakan gerbang XOR, yang sebenarnya Anda hitung Demikian pula, meskipun a ∨ b = ¬ ( ¬ a ∧ ¬ b ) , ketika Anda menerapkan gerbang OR tunggal ini dengan AND dan XOR, Anda akan mendapatkan sedikit gadget kedalaman 3.)$\mathbb{Z}$$a \vee b = \neg (\neg a \wedge \neg b)$

Pernyataan umum adalah: biarkan menjadi polinomial dengan koefisien dalam cincin R , dan anggap φ : R → S adalah cincin homomorfisme. Dengan menerapkan φ untuk setiap koefisien f Anda mendapatkan polinomial dengan koefisien dalam S , yang saya menotasikan f S . Kemudian batas bawah untuk menghitung f S oleh S sirkuit -arithmetic menyiratkan sama rendah menuju komputasi f oleh R sirkuit -arithmetic.$f$$R$$\varphi\colon R \to S$$\varphi$$f$$S$$f_S$$f_S$$S$$f$$R$