Lista de problemas sin resolver en informática

Este artículo presenta una lista de problemas notables sin resolver en informática . Un problema en informática se considera sin resolver cuando no se conoce ninguna solución o cuando los expertos en la materia discrepan sobre las soluciones propuestas.

• Problema P vs NP : El problema P vs NP es una importante cuestión sin resolver en la informática que plantea si todo problema cuya solución puede ser verificada rápidamente por una computadora (NP) también puede ser resuelto rápidamente por una computadora (P). Esta cuestión tiene profundas implicaciones para campos como la criptografía, el diseño de algoritmos y la teoría computacional. ^{[ 1 ]}
• ¿Cuál es la relación entre BQP y NP ?
• Problema NC = P
• NP = problema co-NP
• Problema P = BPP
• P = Problema PSPACE
• Problema L = NL
• Problema PH = PSPACE
• Problema L = P
• Problema L = RL
• Conjeturas sobre juegos únicos
• ¿Es cierta la hipótesis del tiempo exponencial ?
  • ¿Es cierta la hipótesis del tiempo exponencial fuerte (SETH)?
• ¿ Existen las funciones unidireccionales ?
  • ¿Es posible la criptografía de clave pública ?
• Conjetura de rango logarítmico
• Conjetura de Hartmanis-Stearns

• ¿ Es posible realizar la factorización de enteros en tiempo polinomial en una computadora clásica (no cuántica)?
• ¿Es posible calcular el logaritmo discreto en tiempo polinomial en un ordenador clásico (no cuántico)?
• ¿Es posible calcular el vector más corto de una red en tiempo polinomial en una computadora clásica o cuántica?
• ¿Se puede resolver el problema del isomorfismo de grafos en tiempo polinomial en una computadora clásica?

El problema del isomorfismo de grafos consiste en determinar si dos grafos finitos son isomorfos, es decir, si existe una correspondencia biunívoca entre sus vértices y aristas que preserva la adyacencia. Si bien se sabe que el problema pertenece a NP, se desconoce si es NP-completo o si se puede resolver en tiempo polinomial. Esta incertidumbre lo sitúa en una clase de complejidad única, lo que lo convierte en un importante problema abierto en la informática. ^{[ 2 ]}

• ¿ La canonización de grafos es equivalente en tiempo polinomial al problema del isomorfismo de grafos?
• ¿Se pueden reconocer las potencias de las hojas y las potencias de k hojas en tiempo polinomial?
• ¿Se pueden resolver los juegos de paridad en tiempo polinomial?
• ¿Es posible calcular la distancia de rotación entre dos árboles binarios en tiempo polinomial?
• ¿ Se pueden reconocer en tiempo polinomial los grafos de ancho de clique acotado ? ^{[ 3 ]}
• ¿Es posible encontrar una cuasigeodésica cerrada simple en un poliedro convexo en tiempo polinomial? ^{[ 4 ]}
• ¿Es posible encontrar una incrustación simultánea con aristas fijas para dos grafos dados en tiempo polinomial? ^{[ 5 ]}
• ¿Se puede resolver el problema de la suma de raíces cuadradas en tiempo polinomial en el modelo de máquina de Turing?

• Problema de Skolem : ¿Es decidible si una sucesión de recurrencia lineal algebraica tiene un cero?
• El décimo problema de Hilbert sobre el campo de los números racionales

• La conjetura de optimalidad dinámica : ¿Tienen los árboles splay una relación competitiva limitada?
• ¿Es posible 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 multiplicar dos números de n dígitos?
• ¿Cuál es la complejidad temporal promedio más baja posible del algoritmo Shellsort con una secuencia de brecha fija determinista?
• ¿ Se puede resolver 3SUM en tiempo fuertemente subcuadrático, es decir, en tiempo O ( n ^2−ϵ ) para algún ϵ > 0 ?
• ¿Es posible calcular la distancia de edición entre dos cadenas de longitud n en tiempo fuertemente subcuadrático? (Esto solo es posible si la hipótesis del tiempo fuertemente exponencial es falsa).
• ¿Se puede realizar la ordenación X + Y en 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 entre todos los pares de nodos en un tiempo fuertemente subcúbico, es decir, en un tiempo O ( V ^3−ϵ ) para algún ϵ > 0 ?
• ¿ Se puede desaleatorizar el lema de Schwartz-Zippel para la prueba de identidad polinómica ?
• ¿Admite la programación lineal un algoritmo de tiempo fuertemente polinomial ? (Este es el problema n.° 9 de la lista de problemas de Smale ).
• ¿Cuántas consultas se necesitan para cortar el pastel sin envidia ?
• ¿Cuál es la complejidad algorítmica del problema del árbol de expansión mínima ? De forma equivalente, ¿cuál es la complejidad del árbol de decisión del problema del árbol de expansión mínima? Se conoce el algoritmo óptimo para calcular los árboles de expansión mínima , pero se basa en árboles de decisión, por lo que se desconoce su complejidad.
• Conjetura de Gilbert-Pollak : ¿Es la razón de Steiner del plano euclidiano igual a...?${\displaystyle 2/{\sqrt {3}}}$¿

• Conjetura de Barendregt-Geuvers-Klop : ¿Todo sistema de tipos puros débilmente normalizador es también fuertemente normalizador?

• ¿Es decidible la lógica lineal multiplicativa-exponencial ?
• ¿Es cierta la conjetura de Aanderaa-Karp-Rosenberg ?
• Conjetura de Černý : Si un autómata finito determinista con${\displaystyle n}$estados tiene una palabra de sincronización , debe tener una de longitud como máximo${\displaystyle (n-1)^{2}}$¿
• Problema generalizado de la altura de las estrellas : ¿Se pueden expresar todos los lenguajes regulares utilizando expresiones regulares generalizadas con una profundidad de anidamiento limitada de estrellas de 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 dadas de longitud${\displaystyle n}$¿
• ¿Cuál es el estado de completitud de Turing de todos los autómatas celulares elementales únicos ?
• Determinar si la longitud de la palabra mínima no completable de${\displaystyle M}$es polinomial en${\displaystyle l(M)}$, o incluso en${\displaystyle sl(M)}$Se sabe que${\displaystyle M}$es un código de longitud variable si para todos${\displaystyle u_{1},...,u_{n},v_{1},...,v_{m}\in M}$,${\ Displaystyle u_ {1}... u_ {n} = v_ {1}... v_ {m}}$implica${\displaystyle n=m}$y${\displaystyle u_{i}=v_{i}}$a pesar de${\displaystyle 0<i\leq n}$En tales casos, aún desconocemos si existe una cota polinómica. Esto podría debilitar la conjetura de Restivo (ya refutada en general, aunque se desconocen las cotas superiores).
• Determina todos los números enteros positivos${\displaystyle n}$de tal manera que la concatenación de${\displaystyle n}$y${\displaystyle n^{2}}$en base${\displaystyle b}$usos como máximo${\displaystyle k}$caracteres distintos, para fijos${\displaystyle b}$y${\displaystyle k}$.

• Lista de problemas sin resolver en física
• Lista de problemas sin resolver en matemáticas

• Woeginger, Gerhard J. "Problemas abiertos en torno a algoritmos exactos" . Matemáticas Aplicadas Discretas . 156 (2008): 397–405 .
• La lista de problemas abiertos de la RTA – Problemas abiertos en reescritura .
• La lista de problemas abiertos de TLCA : problemas abiertos en el área del cálculo lambda tipado .