En mi opinión, hay dos razones.
En primer lugar, la teoría de la complejidad es un campo relativamente nuevo. No existía antes de la Segunda Guerra Mundial e incluso los conceptos más fundamentales como la integridad de NP no existían antes de la década de 1970.
La segunda razón es que todavía nos faltan técnicas fundamentales para separar las clases de complejidad. En la década de 1970, se demostró que la técnica de separación más común llamada diagonalización no logra separar P y NP porque no puede explicar las máquinas de Turing con diferentes oráculos. Este resultado se extendió más tarde para mostrar que la técnica falla para otros problemas abiertos como P vs PSPACE o EXP vs NP también. Hoy en día, los teóricos de la complejidad se preocupan principalmente por desarrollar nuevas técnicas de separación que no relativicen, es decir, que puedan manejar máquinas de Oracle con diferentes propiedades. Sin embargo, no es improbable que haya una técnica actualmente desconocida que pueda resolver todos los principales problemas abiertos a la vez.
Esto significa que las preguntas más interesantes en la teoría de la complejidad bien podrían resolverse en los próximos años.
- ¿Fue Rijndael / AES el más fuerte de los candidatos históricos de AES? ¿Por qué o por qué no?
- ¿Cuál es el futuro de la programación de computadoras?
- ¿Cuáles son los documentos de investigación más interesantes de Microsoft?
- ¿Cuáles son los documentos de lectura obligatoria en el campo de la visión por computadora para un estudiante en la investigación en el campo?
- ¿Cuáles son los temas de investigación actuales en informática en la nube?
