Algebraic P vs. NP

I suspect that the question under consideration is whether or not $VP=VNP$; this is the problem directly studied by geometric complexity theorists, as I understand their work. This project is described in some detail here (this paper is by Burgisser, Landsberg, Manivel, and Weyman, describing work of Mulmuley and related people)--it is aimed at algebraic geometers; so you will likely be comfortable with it. The description of the complexity problem under consideration is in section 9.

The algebraic $VP$ vs. $VNP$ conjeture is due to Valiant, in this paper and his paper "Reducibility by algebraic projections" which I can't find online at the moment, unfortunately; these are references [63] and [64] in the paper I link to above. Valiant is, as I recall, a very clear writer, so hopefully you will find these papers readable as well.

Essentially, Valiant argues that some algebraic properties of the permanent and related varieties should have complexity-theoretic implications; a reasonable heuristic for this might be the many combinatorial interpretations of the permanent. Unfortunately, as far as I know there are few implications between these algebraic versions of P vs. NP and the problem itself; there are some results assuming GRH. See e.g. this paper by Burgisser.

Hopefully, this is the algebraic analogue of P vs. NP you were looking for.


There's a paper by Michael Shub, On the intractability of Hilbert's Nullstellensatz and an algebraic version of $``{\rm NP}\ne{\rm P}?''$ available at http://www6.cityu.edu.hk/ma/people/smale/pap97.pdf


In Sapir, Mark V.; Birget, Jean-Camille; Rips, Eliyahu Isoperimetric and isodiametric functions of groups. Ann. of Math. (2) 156 (2002), no. 2, 345–466 we proved that P=NP if and only if the word problem in every group with polynomial Dehn function can be solved in polynomial time by a deterministic Turing machine. Thus to show that P=NP one "only" needs to find an algebraic description of finitely presented groups with polynomial Dehn functions (similar to Gromov's description of groups with polynomial growth functions).