Hace poco asistí a una conferencia en la que el ponente mencionó que lo que estaba hablando estaba relacionado con la versión algebraica del $P$ contra. $NP$ problema. ¿Podría alguien explicar lo que significa de forma sencilla o indicarme una fuente adecuada para un matemático no experto? Gracias.
Sospecho que la cuestión que se plantea es si $VP=VNP$ Este es el problema que estudian directamente los teóricos de la complejidad geométrica, según entiendo su trabajo. Este proyecto se describe con cierto detalle aquí (este artículo es de Burgisser, Landsberg, Manivel y Weyman, y describe el trabajo de Mulmuley y otras personas relacionadas); está dirigido a los geómetras algebraicos, por lo que es probable que te sientas cómodo con él. La descripción del problema de complejidad en cuestión se encuentra en la sección 9.
El algebraico $VP$ contra. $VNP$ conjetura se debe a Valiant, en este documento y su artículo "Reducibilidad por proyecciones algebraicas" que, por desgracia, no puedo encontrar en línea en este momento; se trata de las referencias [63] y [64] del artículo que enlazo más arriba. Valiant es, si no recuerdo mal, un escritor muy claro, así que espero que también encuentres estos artículos legibles.
Esencialmente, Valiant argumenta que algunas propiedades algebraicas de la permanente y las variedades relacionadas deberían tener implicaciones teóricas de la complejidad; una heurística razonable para esto podrían ser las muchas interpretaciones combinatorias de la permanente. Desgraciadamente, hasta donde yo sé hay pocas implicaciones entre estas versiones algebraicas de P vs. NP y el problema en sí; hay algunos resultados que suponen GRH. Véase, por ejemplo este documento de Burgisser .
Espero que este sea el análogo algebraico de P vs. NP que estabas buscando.
Hay un artículo de Michael Shub, On the intractability of Hilbert's Nullstellensatz and an algebraic version of $``{\rm NP}\ne{\rm P}?''$ disponible en http://www6.cityu.edu.hk/ma/people/smale/pap97.pdf
En Sapir, Mark V.; Birget, Jean-Camille; Rips, Eliyahu Funciones isoperimétricas e isodiamétricas de grupos. Ann. of Math. (2) 156 (2002), nº 2, 345-466 demostramos que P=NP si y sólo si el problema de la palabra en cada grupo con función de Dehn polinómica puede ser resuelto en tiempo polinómico por una máquina de Turing determinista. Por lo tanto, para demostrar que P=NP uno "sólo" necesita encontrar una descripción algebraica de los grupos de presentación finita con funciones de Dehn polinómicas (similar a la descripción de Gromov de los grupos con funciones de crecimiento polinómicas).
También está la famosa caracterización algebraica de NP de Fagin (Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable de tiempo polinómico. En Complexity of Computation. SIAM-AMS Proceedings. 7, 43--73, 1974):
El problema de pertenencia a una clase abstracta (es decir, cerrada bajo isomorfismos) de sistemas algebraicos finitos está en NP si y sólo si es la clase de todos los modelos finitos de una fórmula de segundo orden de segundo orden del siguiente tipo: $$\exists Q_1\exists Q_2\ldots \exists Q_n (\Theta)$$ donde $Q_i$ es un predicado, y $\Theta$ es una fórmula de primer orden.
Esto también da una caracterización algebraica de P=NP.
También el Problema de Satisfacción de Restricciones ofrece otra aproximación algebraica a P=NP. Ese problema es muy popular en el Álgebra Universal ahora (ver, por ejemplo, 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).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
