Hay miles, si no millones, de problemas abiertos en la informática. Aquí hay una docena de ellos que se me ocurren.
- ¿El no determinismo realmente acelera la computación? (¿P=NP?)
- ¿Pueden resolverse rápidamente los problemas que tienen poco espacio? (¿P = PSPACE?)
- ¿La aleatoriedad realmente acelera la computación? (¿RP=P? ¿PBP=P?)
- ¿Cuánto acelera realmente la computación la explotación de la computación cuántica?