Warum Untergrenzen für Boolesche Schaltungen keine Untergrenzen für arithmetische Schaltungen bedeuten

Meine Frage ist, warum Untergrenzen für Tiefe 3 Boolesche Schaltungen mit Gates "und" und "xor" für Determinante nicht die gleichen Untergrenzen für arithmetische Schaltungen über implizieren ? $\mathbb{Z}$

Was ist falsch an dem folgenden Argument: Sei eine arithmetische Schaltungsberechnungsdeterminante, dann erhalten wir durch Nehmen aller Variablen mod 2 eine Boolesche Schaltungsberechnungsdeterminante. $C$

cc.complexity-theory circuit-complexity arithmetic-circuits Jemanden
quelle

Antworten:

Für arithmetische Schaltungen über Ihr Argument genau richtig. Das gleiche Argument gilt für arithmetische Schaltungen über die keine Brüche wobei ist. $\mathbb{Z}$ $\mathbb{Q}$ $a/b$ $b$

$\mathbb{Q}$ $\mathbb{R}$ $\mathbb{C}$ $\mathbb{F}_{q}$ $q \neq 2$

$\mathbb{Z}$

$\mathbb{Z}$ $a \vee b = \neg (\neg a \wedge \neg b)$

$f$ $R$ $\varphi\colon R \to S$ $\varphi$ $f$ $S$ $f_S$ $f_S$ $S$ $f$ $R$

Joshua Grochow
quelle

b

$b$

b

$b$

a / b \in Q

$a/b \in \mathbb{Q}$

a b^{- 1} (\mod 2)

$ab^{-1} \pmod{2}$

Bedeutet dies, dass der Beweis einer Art Satz wie von-Division (dh, dass Sie nicht durch zwei teilen müssen) bedeutet, dass die unteren Grenzen über C liegen?

Klim

@Klim: Nein. Das Problem ist, dass eine Schaltung über C immer noch irrationale (oder sogar nicht reale) Konstanten verwenden kann, die Sie immer noch nicht "mod 2" nehmen können.

Joshua Grochow