# How is the VP=VNP question in char 2 different from other char? What is the current frontier in regards to this question?

What are the caveats one should be aware of when pursuing VP=VNP question in char 2 compared to other char? What is the current frontier in regards to this question?

The relationship of the VP vs VNP question in different characteristics to Boolean complexity classes depends on the characteristic, but in an obvious way (e.g. Boolean complexity classes defined in terms of a similar characteristic, like $\mathsf{Mod_n P}$).
(Another caveat to be aware of is the distinction between functions over $\mathbb{F}_2$ and formal polynomials over $\mathbb{F}_2$. As functions, $x^2 - x$ and $0$ are the same, but as formal polynomials over $\mathbb{F}_2$ these are distinct. VP and VNP are usually defined in terms of formal polynomials.)
• No, it involves division by 2 (as do the proofs of the #P-hardness of perm). In characteristic 2, perm=det, so if the VNP-completeness proof for perm worked in characteristic 2 then we'd have that VP=VNP over $\mathbb{F}_2$, which implies (by Burgisser) that $\oplus P/poly \subseteq FNC^2/poly$... Jul 28, 2016 at 18:01