Hay miles , si no millones, de problemas abiertos en informática. Aquí hay una docena más o menos fuera de mi cabeza.
- ¿El no determinismo en realidad acelera la computación? (¿P = NP?)
- ¿Se pueden resolver rápidamente los problemas que se pueden resolver con poco espacio? (¿P = PSPACE?)
- ¿La aleatoriedad realmente acelera el cálculo? (¿RP = P? BPP = P?)
- ¿Cuánto la explotación de la computación cuántica realmente acelera la computación? (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 2 ^ {o (n)} tiempo? (La hipótesis del tiempo exponencial)
- ¿Se puede resolver kSAT en 2 ^ {0.9999 n} tiempo para todos los k? (La hipótesis del tiempo exponencial fuerte)
- ¿Se puede resolver 3SUM en tiempo O (n ^ {1.99999})?
- ¿Se puede resolver la clasificación X + Y en el tiempo O (n ^ 2)? ¿En el tiempo O (n ^ {1.99999})?
- ¿Se pueden resolver los caminos más cortos de todos los pares en tiempo O (n ^ {2.99999})?
- ¿Es cierta la conjetura de los juegos únicos?
- ¿Son evasivas las propiedades del gráfico monótono?
- ¿Se pueden calcular los flujos máximos en gráficos planos en tiempo O (n)?
- ¿Se pueden calcular los flujos máximos en gráficos toroidales (no dirigidos, de capacidad unitaria) en O (n ^ {1.49999}) tiempo? O (n \ log n) tiempo? ¿A tiempo?
- ¿Existe un algoritmo implementable para triangular polígonos en tiempo O (n)?
- ¿Existe un algoritmo implementable para decidir si se puede dibujar un gráfico en un toro sin cruces de bordes en el tiempo O (n)?
- ¿Cuál es el conjunto completo de menores prohibidos mínimos para gráficos toroidales? Para gráficos del género 2? Para gráficos de treewidth 4?
- ¿Se puede convertir una gramática arbitraria sin contexto de longitud $ n $ a la forma normal de Chomsky en tiempo O (n ^ {1.9999})? O (n ^ {3/2}) tiempo?
- ¿Son los árboles extendidos dinámicamente óptimos? ¿Existe algún árbol de búsqueda binaria autoajustable en línea que sea dinámicamente óptimo? ¿Existe algún árbol de búsqueda binaria autoajustable en línea que sea dinámicamente óptimo? ¿ Existe algún árbol de búsqueda binaria autoajustable sin conexión que sea 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)? ¿La séptima R (7,7)?
- ¿Existe una prueba verificable por máquina del teorema de la estructura gráfica de Robertson y Seymour? ¿Qué pasa con el 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?
- ¿Hay alguna generalización natural de Getting Over It NP-hard? PSPACE-hard? Indecidible?
- ¿Cuántas lamidas se necesitan para llegar al centro de Tootsie Roll de un Tootsie Pop?
Y esto es solo informática teórica .
- ¿Cómo se podría utilizar la representación del conocimiento y el razonamiento en la ciencia de datos?
- Si los poderes informáticos aumentaran diez veces, ¿cómo afectaría la investigación actual de IA?
- ¿Cuáles son algunos temas de investigación recientes sobre diseño de máquinas?
- ¿Por qué el PageRank es muy alto para los nodos en un gráfico con indegree cero?
- ¿Cuáles son algunos documentos que demuestran el uso de la teoría de la representación en informática?
