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.
$\begingroup$
$\endgroup$
asked Mar 7, 2011 at 22:38
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
2
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 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 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.
Hopefully, this is the algebraic analogue of P vs. NP you were looking for.
answered Mar 8, 2011 at 1:18
-
1$\begingroup$ Hi Daniel, yes, this sounds like what I was looking for. Thanks! $\endgroup$ Commented Mar 8, 2011 at 1:27
-
$\begingroup$ No problem! It seems like pretty cool stuff; I am, alas, not qualified to evaluate how promising these techniques are. $\endgroup$ Commented Mar 8, 2011 at 1:29
$\begingroup$
$\endgroup$
1
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).
-
$\begingroup$ Is there a statement with $RP=NP\iff\dots$? $\endgroup$– TurboCommented Aug 27, 2017 at 19:26
$\begingroup$
$\endgroup$
0
There's a paper by Michael Shub, On the intractability of Hilbert's Nullstellensatz and an algebraic version of $``{\rm NP}\ne{\rm P}?''$.
answered Mar 7, 2011 at 22:45
$\begingroup$
$\endgroup$
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.)