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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
In terms of these complexity classes as a whole, not much is known that distinguishes characteristic 2 from other characteristics. The most frequently arising difference is that the permanent is easy in characteristic 2 (so not VNP-complete unless VP=VNP). (In contrast, the Hamiltonian Cycle polynomial is VNP-complete in all characteristics.)
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}$).
Aside from these (and a few other similar examples like permanent), I'm not sure I know of any proven differences between the different characteristics. I'd be interested to see some!
(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.)
answered Jul 28, 2016 at 2:14
-
$\begingroup$ doesn't the permanent is VNP complete proof work on all characteristics? $\endgroup$– TurboJul 28, 2016 at 17:11
-
1$\begingroup$ 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$... $\endgroup$ Jul 28, 2016 at 18:01