VP versus VNP

For a two-by-two grid containing 1, 2 on the first row and 3, 4 on the second, choose one entry from each row without using a column twice. The two products are 1 times 4 and 2 times 3; adding them gives 10. This sum is called the permanent. With more rows there are many more choices, but a long list of terms might still have a clever short calculation. VP versus VNP asks whether every efficiently described sum of this kind can be computed by a small network of additions and multiplications. The permanent is a central test case. Here arithmetic uses number systems, such as the rationals, in which repeated addition of 1 never gives 0.[1]

Can every compactly specified sum of polynomial terms be evaluated by a polynomial-size arithmetic circuit, or does some such family resist every circuit? An arithmetic circuit combines variables and field constants through additions and multiplications and can reuse a computed value. The two-by-two permanent illustrates the object:$$\operatorname{perm}\begin{pmatrix}a&b\\c&d\end{pmatrix}=ad+bc.$$At $a=1,b=2,c=3,d=4$, it is $10$; the determinant $ad-bc$ is $-2$. For a larger matrix, the permanent sums one product per permutation, selecting one entry in each row and each column. Many displayed terms alone do not imply a large circuit. This page works over characteristic-zero fields, including $\mathbb Q$, where repeated addition of $1$ never gives $0$. A polynomial family has at most polynomially many variables and polynomially bounded degree. It is in $\mathrm{VP}$ if a circuit of size bounded by a fixed power of the family index computes each member. It is in $\mathrm{VNP}$ if it has the form$$\displaystyle f_n(x)=\sum_{e\in\{0,1\}^{m(n)}}g_n(x,e),$$where $m(n)$ is polynomially bounded and $(g_n)$ is in VP. The open separation $\mathrm{VP}\ne\mathrm{VNP}$ is equivalent here to proving that the symbolic permanent has no polynomial-size unrestricted arithmetic-circuit family.[1]

The unrestricted VP versus VNP separation remains open.[1]

The 2026 symmetric-circuit separations depend on model restrictions. They and restricted-depth bounds do not prove the unrestricted characteristic-zero separation.[1]

Listing many terms and computing their total are different tasks. Algebra often compresses a long expression by sharing intermediate results or finding an identity. This problem asks whether compact descriptions of sums can conceal an unavoidable arithmetic cost, even after every such shortcut is allowed. The permanent gives a concrete way to study that tension: each term is easy to form, while the best possible calculation of the whole symbolic sum remains unknown.[1]

VNP formalizes a sum whose individual contributions can be computed efficiently, without granting an efficient way to total all contributions. The permanent’s universal role means that a small circuit for it would also compress the other VNP families, while a superpolynomial lower bound would separate it from VP. Restricted models provide a warning: some known lower-bound methods also make the determinant look hard even though unrestricted circuits compute it efficiently. The goal is therefore a limitation on every arithmetic circuit, with sharing and algebraic identities available, not a limitation on expanding a formula term by term.[1]