Es casi más fácil dar una lista de preguntas resueltas. Aquí hay algunos de la parte superior de mi cabeza y con una lectura rápida de Wikipedia:
- Es P = NP?
- Es P = BPP?
- Es P = NC?
- Es P = RP?
- ¿Es L = NL?
- ¿RP = co-RP?
- ¿NP = co-NP?
- ¿NP = PSPACE?
- Es P = PSPACE? Nadie cree que este sea el caso, pero no podemos probar que no lo sea.
- ¿NP = EXPTIME?
- ¿PSPACE = EXPTIME?
- ¿Están NP y BQP contenidos en el otro?
- ¿Se colapsa la jerarquía polinómica?
- ¿Hay alguna función unidireccional?
- ¿Es cierta la conjetura de los juegos únicos?
- ¿Es verdadera la hipótesis del tiempo exponencial?
Probablemente podría continuar por un tiempo más con búsquedas más extensas, pero esta lista es un buen punto de partida.
Pregunté ¿Cuáles son algunos problemas resueltos interesantes en la teoría de la complejidad computacional? como contrapunto a esta pregunta. Realmente no hay mucho que sepamos, y será interesante ver qué hace realmente la lista.
- ¿Cómo sabemos que la investigación amigable de IA es realmente correcta / significativa?
- ¿Cuáles son las pruebas más importantes que uno debe estudiar en el campo de la informática teórica?
- ¿Qué tipo de problemas informáticos son más divertidos de resolver?
- ¿Cómo puede la investigación de CS, como la investigación de visión por computadora, contribuir a las áreas de astronomía?
- ¿Habrá informáticos en 2047?
