I recently attended a lecture where the speaker mentioned that what he was talking about was connected to the algebraic version of the $P$ vs. $NP$ problem. Could someone explain what that means in a simple way or point me to a source suitable for a non-expert mathematician? Thanks.



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](https://doi.org/10.1137/090765328 "An overview of mathematical issues arising in the geometric complexity theory approach to VP≠VNP. SIAM J. Comput. 40, No. 4, 1179–1209 (2011). zbMATH review at https://zbmath.org/1252.68134") (this paper is by Bürgisser, 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](https://doi.org/10.1145/800135.804419 "Completeness classes in algebra. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing (STOC '79). Association for Computing Machinery, New York, NY, USA, 249–261 (1979).") 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 Bürgisser](https://doi.org/10.1016/S0304-3975(99)00183-8 "Cook's versus Valiant's hypothesis. Theor. Comput. Sci. 235, No. 1, 71–88 (2000). zbMATH review at https://zbmath.org/0943.68070").


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


