Skip to main content
1 of 2
Daniel Litt
  • 23k
  • 5
  • 84
  • 144

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.

Daniel Litt
  • 23k
  • 5
  • 84
  • 144