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? (Sabemos que tiene algún efecto, debido al algoritmo de Grover, pero ¿cuánto? ¿BQP=P?)
- ¿La no uniformidad realmente acelera la computación?
- ¿Se puede resolver 3SAT en [math]2^{o(n)} [/math]tiempo? (La hipótesis del tiempo exponencial)
- ¿Se puede resolver kSAT en [math]O(2^{0.9999 n})[/math] tiempo para todo k? (La hipótesis del tiempo exponencial fuerte)
- ¿Se puede resolver 3SUM en [math]O(n^{1.99999})[/math] tiempo?
- ¿Se puede resolver Sorting X+Y en [math]O(n^2)[/math] tiempo? ¿En [math]O(n^{1.99999})[/math] tiempo?
- ¿Se pueden resolver los caminos más cortos de todos los pares en [math]O(n^{2.99999})[/math]tiempo?
- ¿Es cierta la Conjetura de los Juegos Únicos?
- ¿Se evaden las propiedades de los grafos monótonos?
- ¿Se pueden calcular los flujos máximos en grafos planares en tiempo O(n)?
- ¿Se pueden calcular los flujos máximos en grafos toroidales (no dirigidos y de capacidad unitaria) en tiempo [math]O(n^{1.499})[/math]? ¿[math]O(n log n)[/math] tiempo? O(n) tiempo?
- ¿Existe un algoritmo implementable para triangular polígonos en O(n) tiempo?
- ¿Existe un algoritmo implementable para decidir si un grafo puede ser dibujado en un toroide sin cruces de aristas en O(n) tiempo?
- ¿Cuál es el conjunto completo de mínimos prohibidos para grafos toroidales? ¿Para grafos de género 2? Para los gráficos de treewidth 4?
- ¿Se puede convertir una gramática arbitraria libre de contexto de longitud en forma normal de Chomsky en [math]O(n^{1.9999})[/math] tiempo? ¿[math]O(n^{3/2})[/math] de tiempo?
- ¿Son los árboles de reproducción dinámicamente óptimos? ¿Es cualquier árbol de búsqueda binaria autoajustable en línea dinámicamente óptimo? ¿Es cualquier árbol de búsqueda binaria autoajustable fuera de línea dinámicamente óptimo?
- ¿Se puede calcular el género de un nudo en tiempo polinómico?
- ¿Cuál es el quinto número de Ramsey R(5,5)? ¿El sexto número de Ramsey R(6,6)? El séptimo R(7,7)?
- ¿Existe una prueba comprobable por máquina del teorema de la estructura del grafo de Robertson y Seymour? ¿Qué hay del teorema de clasificación para grupos simples finitos?
- ¿Cuál es la máquina de Turing más pequeña cuyo comportamiento es independiente de ZFC?
- ¿Es alguna generalización natural de Superarlo NP-dura? ¿Difícil para PSPACE? ¿Idecidible?
- ¿Cuántos lametazos se necesitan para llegar al centro del Tootsie Roll de una Tootsie Pop?
Y esto es sólo informática teórica.