Este artículo es una lista de problemas notables sin resolver en informática . Un problema en ciencias de la computación se considera sin resolver 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 de P versus NP
- ¿Cuál es la relación entre BQP y NP ?
- NC = problema P
- NP = problema co-NP
- P = problema de BPP
- P = problema PSPACE
- L = problema NL
- PH = problema de PSPACE
- L = problema P
- L = problema de RL
- Conjetura de juegos únicos
- ¿Es cierta la hipótesis del tiempo exponencial ?
- ¿Es verdadera la hipótesis del tiempo exponencial fuerte (SETH)?
- ¿ Existen funciones unidireccionales ?
- ¿Es posible la criptografía de clave pública ?
- Conjetura del rango logarítmico
Tiempo polinomial versus tiempo no polinomial para problemas algorítmicos específicos
- ¿Se puede realizar la factorización de enteros en tiempo polinomial en una computadora clásica (no cuántica)?
- ¿Se puede calcular el logaritmo discreto en tiempo polinomial?
- ¿Se puede calcular el vector más corto de una red en tiempo polinomial en una computadora clásica o cuántica?
- ¿Se pueden encontrar dibujos planos agrupados en tiempo polinomial?
- ¿Se puede resolver el problema del isomorfismo de la gráfica en tiempo polinomial?
- ¿ Se pueden reconocer los poderes de las hojas y los poderes de las hojas k 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 polinomial?
- ¿Se pueden reconocer gráficos de ancho de camarilla acotado en tiempo polinomial? [1]
- ¿Se puede encontrar un cuasigeodésico cerrado simple en un poliedro convexo en tiempo polinomial? [2]
- ¿Se puede encontrar una incrustación simultánea con bordes fijos para dos gráficos dados en tiempo polinomial? [3]
Otros problemas algorítmicos
- La conjetura de la optimización dinámica : ¿los árboles de expansión tienen una relación competitiva limitada?
- ¿Existe un algoritmo en línea competitivo k para el problema del servidor k ?
- ¿Se puede construir un árbol de búsqueda en profundidad en NC ?
- ¿Se puede calcular la transformada rápida de Fourier en 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 de tiempo promedio de caso más baja posible de Shellsort con una secuencia de intervalo fijo determinista?
- ¿ Se puede resolver 3SUM en un tiempo fuertemente subcuadrático, es decir, en el tiempo O ( n 2 − ϵ ) para algún ϵ> 0 ?
- ¿Se puede calcular la distancia de edición entre dos cadenas de longitud n en un tiempo fuertemente subcuadrático? (Esto solo es posible si la hipótesis del tiempo exponencial fuerte es falsa).
- ¿Se puede realizar la clasificación X + Y en un tiempo o ( n 2 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 algún ϵ> 0 ?
- ¿Se puede desaleatorizar el lema de Schwartz-Zippel para las pruebas de identidad polinomial ?
- ¿ Admite la programación lineal un algoritmo de tiempo fuertemente polinomial ? (Este es el problema n. ° 9 en la lista de problemas de Smale ).
- ¿Cuántas consultas se requieren para cortar un pastel sin envidias ?
- ¿Cuál es el algoritmo para la tabla de búsqueda que genera consistentemente laberintos jugables en el juego Entombed de Atari 2600 de 1982 simplemente a partir de los valores de los cinco píxeles adyacentes a los siguientes que se generarán?
- ¿Cuál es la complejidad algorítmica del problema del árbol de expansión mínimo ? De manera equivalente, ¿cuál es la complejidad del árbol de decisiones del problema MST? Se conoce el algoritmo óptimo para calcular MST , pero se basa en árboles de decisión, por lo que se desconoce su complejidad.
Algoritmos de procesamiento del lenguaje natural
- ¿Existe algún algoritmo de silabificación perfecto en el idioma inglés?
- ¿Existe algún algoritmo de derivación perfecto en el idioma inglés?
- ¿Existe algún algoritmo perfecto de fragmentación de frases en el idioma inglés?
- ¿Cómo pueden las computadoras discernir la ambigüedad de los pronombres en el idioma inglés? (También conocido como Winograd Schema Challenge ).
Teoría del lenguaje de programación
- POPLmark
- Conjetura de Barendregt-Geuvers-Klop
Otros problemas
- Conjetura de Aanderaa-Karp-Rosenberg
- Conjetura de Černý
- Problema generalizado de la altura de las estrellas
- Problema de separación de palabras
Referencias
- ^ Compañeros, Michael R .; Rosamond, Frances A .; Rotics, Udi; Szeider, Stefan (2009), "Clique-width is NP-complete" (PDF) , SIAM Journal on Discrete Mathematics , 23 (2): 909–939, doi : 10.1137 / 070687256 , MR 2519936 , archivado desde el original (PDF ) el 27/02/2019.
- ^ Demaine, Erik D .; O'Rourke, Joseph (2007), "24 Geodesics: Lyusternik – Schnirelmann", Algoritmos de plegado geométrico: enlaces, origami, poliedros , Cambridge: Cambridge University Press, págs. 372–375, doi : 10.1017 / CBO9780511735172 , ISBN 978-0-521-71522-5, Señor 2354878.
- ^ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006), "Embeddings de gráficos simultáneos con bordes fijos" (PDF) , Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Noruega, 22-24 de junio de 2006, Revised Papers (PDF) , Lecture Notes in Computer Science, 4271 , Berlín: Springer, págs. 325–335, doi : 10.1007 / 11917496_29 , MR 2290741.
enlaces externos
- Problemas abiertos sobre algoritmos exactos de Gerhard J. Woeginger , Discrete Applied Mathematics 156 (2008) 397–405.
- La lista RTA de problemas abiertos: problemas abiertos al reescribir .
- La lista de problemas abiertos de la TLCA : problemas abiertos en el cálculo lambda de tipo área .