Comenzaría con lo que llamaría “teoría de la complejidad básica”, es decir, comprender la notación big-O, etc. Esto viene como parte del título universitario estándar de ciencias de la computación. Aquí, cubrirá estructuras de datos, algoritmos, matemáticas discretas, etc.
Luego miraría las teorías y definiciones específicas de las clases de complejidad P y NP.
Comience entonces a observar los fundamentos básicos: el teorema de Cook-Levin y algunos de los estudios de problemas NP-completos generados por Karp.
- ¿Qué es la teoría de tipos en informática?
- Como experto en justicia penal interesado en computadoras, ¿debo aprender el aprendizaje automático u obtener mi certificado Cisco CCNA?
- Si pudieras retroceder en el tiempo con una unidad flash moderna, ¿cómo conseguirías que una computadora la lea?
- ¿UBC, USC o UCI son mejores para la informática de pregrado?
- ¿Qué hace una computadora cuando se congela?
Si llega hasta aquí, tendrá una buena sensación “práctica” del problema P vs NP. Ser capaz de reconocer y clasificar los problemas como estar en NP o no en NP es un buen comienzo. Ser capaz de reconocer problemas NP-hard o NP-complete también es útil.
A continuación, debe obtener una idea de las clases de complejidad co-NP (el lenguaje complementario de NP), L (espacio de registro) y la jerarquía de tiempo polinomial (PH). Puedes encontrar un conjunto muy, muy rico de clases de complejidad en el Complexity Zoo, establecido por primera vez por Scott Aaronson. El complejo zoológico es un poco más complicado de lo que podrías necesitar, pero es bueno “hurgar” un poco para tener al menos una idea de lo que hay ahí fuera.
En este punto, tendrá suficientes antecedentes para comprender un poco de lo que está explorando.
Si realmente quiere estudiar esto en serio, debe hacer un seguimiento de los principales resultados conocidos para el problema P vs NP, específicamente, los trabajos que muestran obstáculos para probar P! = NP. Estos son los trabajos de Baker-Gill-Solovay, que muestran que el uso de técnicas de “relativización” no es probable que lleguen muy lejos; el argumento de “Pruebas naturales” de Rudich y Razborov, y los argumentos de “Algebrización” de Aaronson y Wigderson.
Para apreciar completamente el argumento de las pruebas naturales de Rudich y Razborov, también es útil buscar los resultados de Razborov con respecto a los circuitos booleanos monótonos.
Del mismo modo, al menos debe estar al tanto de los intentos que se han realizado para probar P = NP o P! = NP. En algún lugar hay una página web con una descripción de más de 100 intentos fallidos. (Lo siento, no recuerdo su ubicación en este momento).
En este punto, tiene al menos un trasfondo pasajero en la teoría de la integridad de NP y algunos de los problemas de tratar de resolver el problema. Si decide presentar su propia “prueba” de P = NP o P! = NP, deberá abordar la historia de los documentos de Baker-Gill-Solovay, Rudich-Razborov y Aaronson-Wigderson. Deberá mostrar cómo su prueba supera estas barreras.
Hay dos áreas donde, en mi opinión, si va a haber un avance en el problema P vs NP, entonces el resultado sería en una de estas dos áreas. El primero está en la teoría de la complejidad descriptiva y el siguiente está en la teoría de la complejidad geométrica.
A continuación, debe consultar la “Teoría de la complejidad descriptiva”. Ronald Fagin inició este trabajo, luego Stockmeyer lo mejoró aún más, pero Neil Immerman tiene las contribuciones más ricas en esta área. Su libro de texto “Complejidad descriptiva” no es una lectura particularmente fácil, pero tiene muy buena información.
Finalmente, los avances más recientes en esta área para mostrar promesa es el trabajo de Ketan Mulmuley sobre la teoría de la complejidad geométrica.
Si puede obtener cierto grado de comodidad con todas estas áreas, estará lo suficientemente versado como para hacer contribuciones al campo. Por supuesto, es posible hacer contribuciones significativas sin comprender realmente todas las áreas que mencioné; pero ayuda a asegurarse de que no esté cubriendo el terreno antiguo.
