Un problema en informática se considera no resuelto cuando no se conoce una solución, o cuando los expertos en el campo no están de acuerdo con las soluciones propuestas.
Complejidad computacional
- Problema P versus NP (a menudo escrito como “P = NP”)
- ¿Cuál es la relación entre BQP y NP?
- NC = problema P
- NP = problema co-NP
- P = problema de BPP
- P = problema de PSPACE
- L = problema de NL
- L = problema P
- L = problema RL
- Conjetura de juegos únicos
- ¿Es verdadera la hipótesis del tiempo exponencial?
- ¿Existen funciones unidireccionales? ¿Es posible la criptografía de clave pública?
Tiempo polinómico versus tiempo no polinómico para problemas algorítmicos específicos
- ¿Se puede realizar la factorización de enteros en tiempo polinómico en una computadora clásica (no cuántica)?
- ¿Es completa la factorización entera NP?
- ¿Se pueden encontrar dibujos planos agrupados en tiempo polinómico?
- ¿Se puede calcular el logaritmo discreto en tiempo polinómico?
- ¿Se puede resolver el problema del isomorfismo gráfico en tiempo polinómico?
- ¿Se pueden reconocer los poderes de las hojas y los poderes de las hojas k en el tiempo polinómico?
- ¿Se pueden resolver los juegos de paridad en tiempo polinómico?
- ¿Se puede calcular la distancia de rotación entre dos árboles binarios en tiempo polinómico?
- ¿Se pueden reconocer los gráficos de ancho de camarilla acotado en tiempo polinómico? [1]
- ¿Se puede encontrar un cuasigeodesico simple cerrado en un poliedro convexo en tiempo polinómico? [2]
- ¿Se puede encontrar una incrustación simultánea con bordes fijos para dos gráficos dados en tiempo polinómico? [3]
Otros problemas algorítmicos
- ¿Cuál es el algoritmo más rápido para la multiplicación de dos números de n dígitos?
- ¿Cuál es el algoritmo más rápido para la multiplicación de matrices?
- ¿Se puede aleatorizar el lema de Schwartz-Zippel para la prueba de identidad polinómica?
- ¿Se puede construir un árbol de búsqueda de profundidad primero en Carolina del Norte?
- ¿La programación lineal admite un algoritmo de tiempo fuertemente polinómico? Este es el problema # 9 en la lista de problemas de Smale.
- ¿Cuál es el límite inferior de la complejidad de los algoritmos rápidos de transformación de Fourier? ¿Pueden ser más rápidos que Θ (N log N)?
- La conjetura de la optimización dinámica: ¿los árboles de separación tienen una relación competitiva limitada?
- ¿Podemos calcular la distancia de edición entre dos cadenas de longitud n en un tiempo fuertemente subcuadrático, es decir, en el tiempo O ( n 2 − ϵ) para algún ϵ> 0?
- ¿Existe un algoritmo en línea k-competitivo para el problema del servidor k?
- ¿Se puede hacer la clasificación X + Y en un tiempo estrictamente menor que O ( n 2 log n )?
- ¿Cuántas consultas se requieren para cortar pasteles sin envidia?
- ¿Cuál es la menor complejidad de tiempo en el peor de los casos posible de Shellsort con una secuencia determinista de intervalo fijo?
Teoría del lenguaje de programación
- POPLmark
- Conjetura de Barendregt – Geuvers – Klop
Otros problemas
- Conjetura de Aanderaa – Karp – Rosenberg
- Problema generalizado de altura de estrella
- Problema de palabras separadas
- Posibilidad de hipercomputación
Gracias.