Pourquoi les bornes inférieures des circuits booléens n'impliquent-elles pas les bornes arithmétiques des bornes inférieures

Ma question est pourquoi les bornes inférieures pour les circuits booléens de profondeur 3 avec les portes "et" et "xor" pour le déterminant n'impliquent pas les mêmes bornes inférieures pour les circuits arithmétiques sur ? $\mathbb{Z}$

Quel est le problème avec l'argument suivant: Soit un déterminant de calcul de circuit arithmétique puis en prenant toutes les variables mod 2 nous obtiendrons un déterminant de calcul de circuit booléen. $C$

cc.complexity-theory circuit-complexity arithmetic-circuits Quelqu'un
la source

Réponses:

Pour les circuits arithmétiques sur votre argument est tout à fait exact. Le même argument fonctionne pour les circuits arithmétiques sur qui n'utilisent pas de fractions où est pair. $\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
la source

b

$b$

b

$b$

a / b \in Q

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

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

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

Cela signifie-t-il que prouver un type de théorème comme la division de von (c'est-à-dire que vous n'avez pas besoin de diviser par deux) impliquera des limites inférieures de circuit sur C?

Klim

@Klim: Non. Le problème est qu'un circuit sur C peut toujours utiliser des constantes irrationnelles (ou même non réelles), que vous ne pouvez toujours pas prendre "mod 2".

Joshua Grochow