Math Conjectures

Valiant's VPVP versus VNPVNP Conjecture

OPENLandmarkConjectureProposed 1979 · Standard version

Canonical statement

Over Q\mathbb Q,
VP≠VNP. VP\ne VNP.
The class VPVP consists of polynomial families (fn)(f_n), with fn∈Q[x1,…,xp(n)]f_n\in\mathbb Q[x_1,\ldots,x_{p(n)}] for some polynomial pp, whose degrees and arithmetic-circuit sizes are bounded by polynomials in nn. The class VNPVNP consists of polynomial families (gn)(g_n) for which there are a polynomial qq and a family (hn)∈VP(h_n)\in VP such that
gn(x)=∑y∈{0,1}q(n)hn(x,y). g_n(x)=\sum_{y\in\{0,1\}^{q(n)}}h_n(x,y).
View source LaTeX
Over \(\mathbb Q\),
\[
  VP\ne VNP.
\]
The class \(VP\) consists of polynomial families
\((f_n)\), with
\(f_n\in\mathbb Q[x_1,\ldots,x_{p(n)}]\) for some polynomial \(p\),
whose degrees and arithmetic-circuit sizes are bounded by polynomials in
\(n\). The class \(VNP\) consists of polynomial families \((g_n)\) for
which there are a polynomial \(q\) and a family \((h_n)\in VP\) such
that
\[
  g_n(x)=\sum_{y\in\{0,1\}^{q(n)}}h_n(x,y).
\]
TCS-007:[Valiant1979Completeness][Burgisser2000][MulmuleySohoni2001GCT][OpenAI2026TenAdvances]
Theoretical computer scienceAlgebra and representation theory

Notes

Valiant's conjecture is the algebraic analogue of PP versus NPNP. Over Q\mathbb Q, VPVP consists of families of polynomially bounded degree polynomials computable by polynomial-size arithmetic circuits, and VNPVNP of families obtained from VPVP families by summing over all Boolean assignments to auxiliary variables; the conjecture asserts VP≠VNPVP\ne VNP. Both classes and their completeness theory were introduced by Valiant in 1979, who proved that the permanent family is VNPVNP-complete under projections [Valiant1979Completeness].

Completeness concentrates the question in a single polynomial: VP≠VNPVP\ne VNP over Q\mathbb Q if and only if the permanent has no polynomial-size arithmetic circuits. A stronger concrete target, the permanent-versus-determinant problem, asks for superpolynomial determinantal complexity of the permanent. The structural theory is developed at length by Bürgisser [Burgisser2000], and the geometric complexity theory program of Mulmuley and Sohoni proposes to attack these separations with representation theory and algebraic geometry [MulmuleySohoni2001GCT].

Despite these frameworks, no superpolynomial lower bound on general arithmetic circuits is known for the permanent or for any explicit VNPVNP family, and the conjecture remains open.

Proof-claim watch (1)

Permanent arithmetic-circuit and formula lower bounds

Grade C

Important lower-bound claim pending verification; the polynomial bounds do not imply \(VP\ne VNP\).

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.