Question

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.

Answer 1

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.

Answer 2

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).

Answer 3

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

Answer 4

There is also the famous algebraic characterization of NP by Fagin (Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation. SIAM-AMS Proceedings. 7, 43--73, 1974):

The membership problem for an abstract (i.e. closed under isomorphisms) class of finite algebraic systems is in NP if and only if it is the class of all finite models of a second-order formula of the following type: $$\exists Q_1\exists Q_2\ldots \exists Q_n (\Theta)$$ where $Q_i$ is a predicate, and $\Theta$ is a first-order formula.

This also gives an algebraic characterization of P=NP. Also the Constraint Satisfaction Problem gives another algebraic approach to P=NP. That problem is very popular in Universal Algebra now (see, for example, Barto, Libor, Kozik, Marcin, Constraint satisfaction problems of bounded width. 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), 595–603, IEEE Computer Soc., Los Alamitos, CA, 2009.)