Las pruebas de la factorización entera están en $P$

Question

Peter Sarnak cree que la factorización de enteros está en $P$ . Es un problema abierto bien conocido en TCS para identificar la clase de complejidad real de la factorización de enteros. Echa un vistazo a este enlace para las conferencias de Peter Sarnak donde menciona que hace no cree que el factoring no esté en $P$ .

¿Qué pruebas hay de que la factorización entera esté en $P$ aparte del hecho de que la factorización polinómica está en $P$ ?

Answer 1

No creo que haya ninguna prueba convincente de que la factorización de enteros pueda hacerse en tiempo polinómico. Es cierto que la factorización de polinomios puede serlo, pero muchas cosas son mucho más fáciles para los polinomios que para los enteros, y no veo ninguna razón para creer que estos anillos deban tener siempre la misma complejidad computacional. (Curiosamente, si crees eso, significa que el problema del vector de red más corto también debería poder resolverse eficientemente, pero no parece que te diga nada sobre los logaritmos discretos. Esto me desconcierta, ya que los paralelismos entre la factorización y los logaritmos discretos también son fuertes). También es cierto que la prueba de primalidad se puede hacer en tiempo polinómico, pero ese es un problema fundamentalmente diferente: cuando un módulo es primo, tiene enormes consecuencias para la aritmética modular, y no es difícil probar la primalidad buscando esas consecuencias, pero los métodos reales no arrojan ninguna luz sobre la factorización.

Por otra parte, tampoco hay pruebas convincentes de que la factorización no pueda hacerse en tiempo polinómico (véase http://research.microsoft.com/~cohn/Thoughts/factoring.html para más detalles al respecto).

Con nuestro nivel actual de conocimientos, considero que la complejidad de la factorización es una cuestión de opinión, especulación e ilusión, no de argumentos basados en principios. En cambio, hay muy buenas razones por las que la hipótesis de Riemann debería ser cierta, y buenas razones por las que P no debería ser igual a NP. Desde luego, estoy abierto a argumentos que disten mucho de ser pruebas rigurosas, pero nunca he oído ninguno convincente sobre la complejidad de la factorización.

Mi interpretación de la creencia de Sarnak no es que vea buenas razones que otros no aprecian. Más bien, le parece plausible, y quizá le moleste un poco que mucha gente crea firmemente lo contrario sin una buena razón, por lo que se empeña en expresar una opinión firme.