Lista de problemas no resueltos en informática

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

Complejidad computacional

Problema P versus NP
¿Cuál es la relación entre BQP y NP ?
Problema NC=P
NP = problema co-NP
P = problema BPP
P = problema PSPACE
Problema L = NL
Problema PH = PSPACE
Problema L=P
Problema L = RL
Conjetura de juegos únicos
¿Es verdadera 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 de rango logarítmico

Tiempo polinomial versus tiempo polinomial no determinista para problemas algorítmicos específicos

¿Es posible realizar la factorización de números enteros en tiempo polinomial en una computadora clásica (no cuántica)?
¿Se puede calcular el logaritmo discreto en tiempo polinomial en una computadora clásica (no cuántica)?
¿Es posible calcular el vector más corto de una red en tiempo polinomial en una computadora clásica o cuántica?
¿Puede el problema del isomorfismo de grafos resolverse en tiempo polinomial?
¿El tiempo polinomial de canonización de grafos es equivalente al problema de isomorfismo de grafos?
¿Es posible reconocer potencias de hojas y potencias de $k hojas en tiempo polinomial?$
¿Es posible resolver juegos de paridad en tiempo polinomial?
¿ Se puede calcular la distancia de rotación entre dos árboles binarios en tiempo polinomial?
¿Es posible reconocer gráficos de ancho de camarilla acotado en tiempo polinomial? ^[1]
¿Se puede encontrar una cuasigeodésica cerrada simple en un poliedro convexo en tiempo polinomial? ^[2]
¿Es posible encontrar una incrustación simultánea con aristas fijas para dos gráficos dados en tiempo polinomial? ^[3]
¿Es posible resolver el problema de la suma de la raíz cuadrada en tiempo polinomial en el modelo de máquina de Turing?

Otros problemas algorítmicos

La conjetura de optimalidad dinámica : ¿tienen los árboles splay 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 brecha fija determinista?
¿Es posible resolver 3SUM en un tiempo fuertemente subcuadrático, es decir, en un tiempo $O (n 2-ϵ)$ para algún $ϵ>0$ ?
¿Es posible 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).
¿Es posible realizar la ordenació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 ?
¿Es posible 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$ ?
¿ Es posible desaleatorizar el lema de Schwartz-Zippel para pruebas de identidad polinomial ?
¿ La programación lineal admite un algoritmo de tiempo fuertemente polinomial ? (Éste 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ínimo ? 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 : ¿El coeficiente de Steiner del plano euclidiano es igual a ? $2/{\sqrt {3}}$

Teoría de lenguajes de programación

Otros problemas

¿Es verdadera la conjetura de Aanderaa-Karp-Rosenberg ?
Conjetura de Černý : Si un autómata finito determinista con estados tiene una palabra de sincronización , ¿debe tener una de longitud como máximo ? ${\estilo de visualización n}$ $(n-1)^{2}$
Problema generalizado de altura de estrella : ¿Pueden todos los lenguajes regulares expresarse utilizando expresiones regulares generalizadas con una profundidad de anidamiento limitada de estrellas Kleene ?
Problema de separación de palabras : ¿cuántos estados se necesitan en un autómata finito determinista que se comporta de manera diferente en dos cadenas de longitud dadas ? ${\estilo de visualización n}$
¿Cuál es el estado de completitud de Turing de todos los autómatas celulares elementales únicos ?

Referencias

^ Fellows, Michael R. ; Rosamond, Frances A. ; Rotics, 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 el original (PDF) el 2019-02-27.
^ Demaine, Erik D.; O'Rourke , Joseph (2007), "24 Geodésicas: 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, Sr. 2354878.
^ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006), "Incrustaciones simultáneas de grafos con aristas fijas" (PDF) , Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Noruega, 22-24 de junio de 2006, Documentos revisados (PDF) , Lecture Notes in Computer Science, vol. 4271, Berlín: Springer, pp. 325–335, doi :10.1007/11917496_29, ISBN 978-3-540-48381-6, Sr. 2290741.

Enlaces externos

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