Reformulemos un poco la pregunta.
“ ¿Qué debo hacer para mejorar significativamente mis posibilidades de contribuir significativamente al campo de la complejidad computacional? ”
Ahí.
- ¿Por qué las matemáticas son importantes para los informáticos?
- ¿Cómo podemos abordar para resolver el problema de 'Infinite House of Pancakes' de Google Code Jam 2015?
- ¿Cuál es el problema P vs NP?
- ¿Es correcto que 'todos los lenguajes de computadora converjan a LISP'? ¿Por qué?
- Cómo responder a las consultas de rango medio de manera eficiente
Entonces, lo que debe hacer, con toda probabilidad, es estudiar matemáticas y ciencias de la computación para obtener una licenciatura, comprender las cosas lo suficientemente bien como para obtener buenas calificaciones y luego convertirlo en un sólido programa de posgrado en complejidad computacional.
Lo que necesitas no es “literatura”. Leer libros es genial, pero dominar un dominio profundo requiere más que solo leer libros y papeles. Necesita desarrollar las habilidades de un investigador en matemáticas: habilidades para resolver problemas, experiencia en el dominio profundo y la intuición y la experiencia para elegir sabiamente los problemas a abordar. Ir directamente después de P vs NP, por ejemplo, no es un síntoma de tener ese tipo de experiencia.
Estudiar minuciosamente “Complejidad computacional: un enfoque moderno” de Arora y Barak no es una mala manera de familiarizarse con los conceptos básicos del campo, así que definitivamente hágalo si el dominio lo atrae. Pero no es suficiente comenzar a escribir documentos para FOCS o STOC.
A riesgo de afirmar lo obvio: nadie sabe cómo resolver el problema P vs NP, por lo que preguntar qué se necesita para resolverlo es como preguntar qué libros necesita leer para construir una nave espacial hiperdrive intergaláctica. Los objetivos audaces son geniales, pero son mejores si de alguna manera se basan en la realidad.
Entonces, puede preguntarse por qué es posible que alguien no pueda resolver P vs NP inmediatamente después de leer los primeros tres capítulos de Arora-Barak. Bueno, ciertamente es posible, no puedo probar que no lo sea. Pero no es de ninguna manera un plan razonable. Aprenda el campo y tendrá una apreciación mucho mejor de lo que se necesita para probar los resultados sobre las clases de complejidad y cuáles son los obstáculos (como la relativización o las pruebas naturales) para demostrar que P es o no es igual a NP.
