<p>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.)</p>

<p>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}$).</p>

<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!</p>

<p>(Another caveat to be aware of is the distinction between <em>functions</em> over $\mathbb{F}_2$ and <em>formal polynomials</em> 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.)</p>

CC BY-SA 3.0
2016-07-28T17:11:57.080Z
doesn't the permanent is VNP complete proof work on all characteristics?
Turbo
CC BY-SA 3.0
2016-07-28T18:01:03.220Z
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$...
Joshua Grochow
CC BY-SA 3.0
2016-07-28T02:14:23.797Z
2016-07-28T02:14:23.797Z
Joshua Grochow
<p>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?</p>

<cc.complexity-theory><complexity-classes><complexity>
How is the VP=VNP question in char 2 different from other char? What is the current frontier in regards to this question?
SorcererofDM
# How is the VP=VNP question in char 2 different from other char? What is the current frontier in regards to this question?

(Asked by: username_0 on 2016-07-28)

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?

**Tags:** cc.complexity-theory, complexity-classes, complexity


---

## 1 answers

### Answer by username_1 on 2016-07-28. Score: 6

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.)

> **Comments:**
> **username_2**: doesn't the permanent is VNP complete proof work on all characteristics?  
> **username_1**: 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$...  

---

