Lista de problemas sin resolver en informática

Lista de problemas computacionales sin resolver

Este artículo es una lista de problemas notables sin resolver en informática . Un problema en informática se considera no resuelto cuando no se conoce la solución o cuando los expertos en el campo no están de acuerdo sobre las soluciones propuestas.

Complejidad computacional

• Problema de P versus NP
• ¿ Cuál es la relación entre BQP y NP ?
• NC = P problema
• NP = problema co-NP
• P = problema de BPP
• P = problema PSPACE
• L = problema de NL
• PH = problema de PSPACE
• L = P problema
• L = problema RL
• Conjetura de juegos únicos
• ¿Es cierta la hipótesis del tiempo exponencial ?
  • ¿Es cierta la hipótesis del tiempo exponencial fuerte (SETH)?
• ¿Existen funciones unidireccionales ?
  • ¿ Es posible la criptografía de clave pública ?
• Conjetura de rango logarítmico

Tiempo polinómico versus polinómico no determinista 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)?
• ¿Se puede calcular el logaritmo discreto en tiempo polinómico en una computadora clásica (no cuántica)?
• ¿Se puede calcular el vector más corto de una red en tiempo polinómico en una computadora clásica o cuántica?
• ¿Se puede resolver el problema del isomorfismo gráfico en tiempo polinómico?
• ¿ Se pueden reconocer las potencias de las hojas y las k -hojas en tiempo polinomial?
• ¿Se pueden resolver los juegos de paridad en tiempo polinomial?
• ¿Se puede calcular la distancia de rotación entre dos árboles binarios en tiempo polinómico?
• ¿Se pueden reconocer gráficas de ancho de camarilla acotado en tiempo polinómico? ^[1]
• ¿Se puede encontrar una cuasigeodésica cerrada simple en un poliedro convexo en tiempo polinómico? ^[2]
• ¿Se puede encontrar una incrustación simultánea con aristas fijas para dos gráficos dados en tiempo polinómico? ^[3]
• ¿Se puede resolver el problema de la suma de raíces cuadradas en tiempo polinomial en el modelo de la máquina de Turing?

Otros problemas algorítmicos

• La conjetura de la optimización dinámica : ¿los árboles splay tienen una relación competitiva acotada?
• ¿Se puede construir un árbol de búsqueda en profundidad en NC ?
• ¿Se puede calcular la transformada rápida de Fourier en un tiempo o ( n log n ) ?
• ¿ Cuál es el algoritmo más rápido para la multiplicación de dos números de n dígitos?
• ¿Cuál es la complejidad temporal promedio más baja posible de Shellsort con una secuencia de espacio fijo determinista?
• ¿Se puede resolver 3SUM en tiempo fuertemente subcuadrático, es decir, en tiempo O ( n ^2−ϵ ) para algunos ϵ>0 ?
• ¿Se puede calcular la distancia de edición entre dos cadenas de longitud n en un tiempo fuertemente subcuadrático? (Esto sólo es posible si la hipótesis del tiempo exponencial fuerte es falsa).
• ¿Se puede realizar la clasificación X + Y en el tiempo o ( n ² log n ) ?
• ¿ Cuál es el algoritmo más rápido para la multiplicación de matrices ?
• ¿Se pueden calcular los caminos más cortos de todos los pares en un tiempo fuertemente subcúbico, es decir, en el tiempo O ( V ^3−ϵ ) para algunos ϵ>0 ?
• ¿ Se puede desaleatorizar el lema de Schwartz-Zippel para pruebas de identidad polinómica ?
• ¿ La programación lineal admite un algoritmo de tiempo fuertemente polinómico ? (Este es el problema número 9 en la lista de problemas de Smale ).
• ¿ Cuántas consultas se requieren para cortar un pastel sin envidia ?
• ¿ Cuál es la complejidad algorítmica del problema del árbol de expansión mínima ? De manera equivalente, ¿cuál es la complejidad del árbol de decisión del problema MST? Se conoce el algoritmo óptimo para calcular los MST , pero se basa en árboles de decisión, por lo que se desconoce su complejidad.
• Conjetura de Gilbert-Pollack sobre la relación de Steiner del plano euclidiano

Teoría del lenguaje de programación

• marca POPL
• Conjetura de Barendregt-Geuvers-Klop

Otros problemas

• Conjetura de Aanderaa-Karp-Rosenberg
• Conjetura de Černý
• Problema generalizado de altura de las estrellas.
• problema de separar palabras

Referencias

1. Becarios, Michael R .; Rosamond, Frances A .; Róticos, Udi; Szeider, Stefan (2009), "El ancho de camarilla es NP completo" (PDF) , SIAM Journal on Discrete Mathematics , 23 (2): 909–939, doi :10.1137/070687256, MR  2519936, S2CID  18055798, archivado desde original (PDF) el 2019-02-27.
2. Demaine, Erik D .; O'Rourke, Joseph (2007), "24 Geodésicas: Lyusternik – Schnirelmann", Algoritmos de plegado geométrico: vínculos, origami, poliedros , Cambridge: Cambridge University Press, págs. 372–375, doi :10.1017/CBO9780511735172, ISBN 978-0-521-71522-5, señor  2354878.
3. Gassner, Isabel; Jünger, Michael; Percán, Merijam; Schaefer, Marcos; Schulz, Michael (2006), "Incrustaciones simultáneas de gráficos con bordes fijos" (PDF) , Conceptos teóricos de grafos en informática: 32º taller internacional, WG 2006, Bergen, Noruega, 22 al 24 de junio de 2006, artículos revisados ​​(PDF) , Apuntes de conferencias sobre informática, vol. 4271, Berlín: Springer, págs. 325–335, doi :10.1007/11917496_29, ISBN 978-3-540-48381-6, señor  2290741.

enlaces externos

• Problemas abiertos en torno a algoritmos exactos de Gerhard J. Woeginger , Discrete Applied Mathematics 156 (2008) 397–405.
• La lista de problemas abiertos de RTA: problemas abiertos en la reescritura .
• "La lista de problemas abiertos de TLCA: problemas abiertos en cálculo lambda de área tipificada ".