¿Principales problemas no resueltos en informática teórica?

Wikipedia solo enumera dos problemas bajo "problemas no resueltos en informática" :

• P = NP?
• La existencia de funciones unidireccionales

¿Cuáles son otros problemas importantes que deberían agregarse a esta lista?

Reglas:

1. Solo un problema por respuesta
2. Proporcione una breve descripción y los enlaces relevantes.

¿Se puede multiplicar por matrices en operaciones ?n O ( n 2$n$$n$$O(n^2)$

El exponente del límite superior más conocido incluso tiene un símbolo especial, . Actualmente es aproximadamente 2.376, según el algoritmo Coppersmith-Winograd . Una buena visión general del estado del arte es Sara Robinson, Toward an Optimal Algorithm for Matrix Multiplication , SIAM News, 38 (9), 2005.$\omega$$\omega$

Actualización: Andrew Stothers (en su tesis de 2010 ) mostró que , que fue mejorada por Virginia Vassilevska Williams (en una preimpresión de julio de 2014 ) a . Estos límites se obtuvieron mediante un análisis cuidadoso de la técnica básica de Coppersmith-Winograd.ω < $\omega < 2.3737$$\omega < 2.372873$

Actualización adicional (30 de enero de 2014): François Le Gall ha demostrado que en un artículo publicado en ISSAC 2014 ( preprint arXiv ).$\omega < 2.3728639$

¿Es el isomorfismo gráfico en P?

La complejidad del isomorfismo gráfico (IG) ha sido una pregunta abierta durante varias décadas. Stephen Cook lo mencionó en su artículo de 1971 sobre NP-completitud de SAT .

La determinación de si dos gráficos son isomórficos generalmente se puede hacer rápidamente, por ejemplo, mediante software como nautyy saucy. Por otro lado, Miyazaki construyó clases de instancias para las cuales nautyprobablemente requiere tiempo exponencial.

Read y Corneil revisaron los muchos intentos de abordar la complejidad de GI hasta ese punto: The Graph Isomorphism Disease , Journal of Graph Theory 1 , 339–363, 1977.

No se sabe que GI esté en co-NP, pero existe un protocolo aleatorio simple para Graph Non-Isomorphism (GNI). Por lo tanto, se cree que GI (= co-GNI) está "cerca de" NP co-NP.${}\cap{}$

Por otro lado, si GI es NP-completo, entonces la Jerarquía Polinómica se colapsa. Por lo tanto, es poco probable que GI tenga NP completo. (Boppana, Håstad, Zachos, ¿co-NP tiene pruebas interactivas cortas?, IPL 25 , 127–132, 1987)

Shiva Kintali tiene una buena discusión sobre la complejidad de GI en su blog.

Laszlo Babai demostró que el isomorfismo gráfico está en tiempo subexponencial .

Complejidad de Factoring

¿Está factorizando en ?$\mathsf{P}$

• ¿Consecuencias de factorizar estar en P?
• ¿Se sabe que los problemas PRIMES, FACTORING son P-hard?
• ¿Cuáles son las consecuencias de factorizar ser NP-completo?
• P con oráculo de factorización de enteros
• La evidencia de factorización de enteros está en P (en MO )

P = BPP?

¿Existe una regla pivotante para el algoritmo simplex que produzca el peor tiempo de ejecución polinomial? Más en general, ¿hay algún algoritmo fuertemente polinómico para la programación lineal?

La hipótesis del tiempo exponencial (ETH) afirma que resolver SAT requiere un tiempo exponencial de 2 ^{Ω (n)} . ETH implica muchas cosas, por ejemplo que SAT no está en P, por lo que ETH implica P ≠ NP. Ver Impagliazzo, Paturi, Zane, ¿Qué problemas tienen una complejidad fuertemente exponencial? , JCSS 63, 512–530, 2001.

ETH se cree ampliamente, pero es probable que sea difícil de probar, ya que implica muchas otras separaciones de clases de complejidad.

Immerman y Vardi muestran que la lógica de punto fijo captura PTIME en la clase de estructuras ordenadas . Uno de los mayores problemas abiertos en la teoría de la complejidad descriptiva es si se puede eliminar la dependencia del pedido:

¿Existe una lógica que capture PTIME?

En pocas palabras, una lógica que captura PTIME es un lenguaje de programación para problemas de gráficos que funciona directamente en la estructura del gráfico y no tiene acceso a la codificación de los vértices y bordes, de modo que se cumple lo siguiente:

1. cualquier programa sintácticamente correcto modela un problema de gráfico computable en tiempo polinómico y
2. cualquier problema de gráfico computable en tiempo polinómico puede ser modelado por un programa sintácticamente correcto.

Si no hay lógica que capture PTIME, entonces ya que NP es capturado por lógica existencial de segundo orden. Una lógica que captura PTIME proporcionaría un posible ataque a P vs NP.$P \neq NP$

Vea el blog de Lipton para una discusión informal y M. Grohe: The Quest for a Logic Capturing PTIME (LICS 2008) para una encuesta más técnica.

¿Es cierta la conjetura de los juegos únicos ?
Y: dado que existen algoritmos de aproximación de tiempo sub-exponenciales para juegos únicos , ¿dónde descansa finalmente el problema en términos del panorama de complejidad?

Permanente versus determinante

La pregunta permanente versus determinante es interesante debido a dos hechos. Primero, el permanente de una matriz cuenta el número de coincidencias perfectas en un gráfico bipartito. Por lo tanto, el permanente de dicha matriz es # P-Complete. Al mismo tiempo, la definición de lo permanente es muy similar a la del determinante, en última instancia diferente solo por un simple cambio de signo. Es bien sabido que los cálculos determinantes se encuentran en P. Estudiar la diferencia entre lo permanente y lo determinante, y cuántos cálculos determinantes se requieren para calcular el discurso permanente sobre P versus #P.

¿Podemos calcular la FFT en mucho menos tiempo que ?$O(n \log n)$

En el mismo sentido (muy) general, hay muchas preguntas para mejorar los tiempos de ejecución de muchos problemas o algoritmos clásicos: por ejemplo, ¿se pueden resolver todos los pares de rutas más cortas (APSP) en hora?$O(n^{3-\epsilon})$

Editar: APSP se ejecuta a tiempo "donde las adiciones y comparaciones de reales son costos unitarios (pero todas las demás operaciones tienen un costo típico costo logarítmico) ": http://arxiv.org/pdf/1312.6680v2.pdf$(\frac{n^3}{2^{\Omega(log n)^{1/2}}})$

La conjetura de la optimización dinámica para árboles de separación.

O, más en general: ¿hay algún árbol de búsqueda binario dinámico en línea O (1) competitivo?

Un algoritmo determinista de tiempo lineal para el problema del árbol de expansión mínimo .

NP versus co-NP

La pregunta NP versus co-NP es interesante porque NP ≠ co-NP implica P ≠ NP (ya que P está cerrado bajo el complemento). También se relaciona con la "dualidad": separación entre encontrar / verificar ejemplos y encontrar / verificar contraejemplos. De hecho, probar que hay una pregunta tanto en NP como en co-NP es nuestra primera buena evidencia de que un problema que parece estar fuera de P probablemente tampoco sea NP-Completo.

¿Hay problemas que las computadoras paralelas no pueden resolver de manera eficiente?

No se sabe que los problemas que son P-completos sean paralelizables. Los problemas P-completos incluyen Horn-SAT y programación lineal. Pero probar que este es el caso requeriría separar alguna noción de problemas paralelizables (como NC o LOGCFL) de P.

Los diseños de procesadores de computadoras están aumentando el número de unidades de procesamiento, con la esperanza de que esto produzca un rendimiento mejorado. Si los algoritmos fundamentales, como la programación lineal, no son inherentemente paralelizables, entonces hay consecuencias significativas.

¿Todas las tautologías proposicionales tienen pruebas de Frege de tamaño polinómico?

Posiblemente el principal problema abierto de la complejidad de la prueba : demuestre límites inferiores del tamaño súper polinomial en las pruebas proposicionales (llamadas también pruebas de Frege).

Informalmente, un sistema de prueba de Frege es solo un sistema de prueba proposicional estándar para probar tautologías proposicionales (se aprende en un curso de lógica básica), que tiene axiomas y reglas de deducción, donde las líneas de prueba se escriben como fórmulas. El tamaño de una prueba de Frege es el número de símbolos necesarios para anotar la prueba.

El problema entonces pregunta si hay una familia de fórmulas tautológicas proposicionales para las cuales no hay un polinomio tal que el tamaño mínimo de prueba de Frege de sea ​​como máximo , para todos (donde denota el tamaño de la fórmula ).$(F_n)_{n=1}^\infty$$p$$F_n$$p(|F_n|)$$n=1,2,\ldots$$|F_n|$$F_n$

Definición formal de un sistema a prueba de Frege

Definición (regla de Frege) Una regla de Frege es una secuencia de fórmulas proposicionales , para , escrita como . En caso de que , la regla de Frege se llama esquema de axioma . Una fórmula se dice que es derivado por la regla de si son todos los casos de sustitución de , por alguna asignación a los las variables (es decir, hay fórmulas $A_0(\overline x),\ldots,A_k(\overline x)$$k \le 0$$\frac{A_1(\overline x), \ldots,A_k(\overline x)}{A_0(\overline x)}$$k = 0$$F_0$$F_1,\ldots,F_k$$F_0,\ldots,F_k$$A_1,\ldots,A_k$$\overline x$$B_1,\ldots,B_n$ modo que para todos . La regla Frege se dice que es sonido si cada vez que una asignación satisface las fórmulas en el lado superior , entonces también satisface la fórmula en el lado inferior .$F_i = A_i(B_1/x_1,\ldots,B_n/x_n),$$i=0,\ldots,k$$A_1,\ldots,A_k$$A_0$

Definición (prueba de Frege) Dado un conjunto de reglas de Frege, una prueba de Frege es una secuencia de fórmulas de tal manera que cada línea de prueba es un axioma o se deriva de una de las reglas de Frege de líneas de prueba anteriores. Si la secuencia termina con la fórmula , entonces la prueba se dice que es una prueba de . El tamaño de una prueba de Frege es el tamaño total de todas las fórmulas en la prueba.$A$$A$

Un sistema de prueba se dice que es implicationally completa si para todo conjunto de fórmulas , si implica semánticamente , entonces no es una prueba de usando los axiomas (posiblemente) de . Se dice que un sistema de prueba es sólido si admite pruebas de solo tautologías (cuando no se utilizan axiomas auxiliares, como en la anterior).$T$$T$$F$$F$$T$$T$

Definición (sistema de prueba de Frege) Dado un lenguaje proposicional y un conjunto finito de reglas Frege de sonido, se dice que es un sistema a prueba de Frege , si es implicationally completa.$P$$P$$P$

Tenga en cuenta que una prueba de Frege siempre es válida, ya que se supone que las reglas de Frege son válidas. No necesitamos trabajar con un sistema de prueba de Frege específico, ya que un resultado básico en la complejidad de la prueba establece que cada dos sistemas de prueba de Frege, incluso en diferentes idiomas, son polinomialmente equivalentes [Reckhow, tesis doctoral, Universidad de Toronto, 1976].

Establecer límites inferiores en las pruebas de Frege podría verse como un paso hacia la prueba de , ya que si esto es cierto, entonces ningún sistema de prueba proposicional (incluido Frege) puede tener pruebas de tamaño polinomiales para todas las tautologías.$NP \neq coNP$

¿Podemos calcular la distancia de edición entre dos cadenas de longitud en tiempo subcuadrático, es decir, en el tiempo para algún ?$n$$O(n^{2-\epsilon})$$\epsilon>0$

¿Existen realmente algoritmos de tiempo subcuadrático (es decir, tiempo para algunos constantes para problemas difíciles de 3SUM ?$O(n^{2-\delta})$$\delta>0$

En 2014, Grønlund y Pettie describieron un algoritmo determinista para 3SUM que se ejecuta en el tiempo . Aunque este es un resultado importante, la mejora sobre es solo (sub) logarítmica. Además, no se conocen algoritmos subcuadráticos similares para la mayoría de los otros problemas difíciles de 3SUM.$O(n^2/(\log n/\log \log n)^{2/3})$$O(n^2)$

BQP = P?

También: NP contenido en BQP?

Sé que esto violó las reglas al tener dos preguntas en la respuesta, pero cuando se toma con la pregunta P vs NP, no son necesariamente preguntas independientes.

1. Conjetura del isomorfismo. (¿Son todos los problemas NP completos el "mismo" problema?)
2. ¿Se puede basar la criptografía en un problema de NP completo?

y, un poco más lejos de la corriente principal:


3. ¿Cuál es el tamaño de NP dentro de EXP?

(Informalmente, si tiene todos los problemas en EXP en una mesa y elige uno de manera uniforme al azar, ¿cuál es la probabilidad de que el problema que elija esté también en NP? Esta pregunta se ha formalizado por la noción de medida limitada por recursos Se sabe que P tiene una medida cero dentro de EXP, es decir, el problema que recogió de la tabla seguramente no está en P.)

¿Cuál es la aproximabilidad de Metric TSP ? El algoritmo de Christofides de 1975 es un algoritmo de aproximación de tiempo polinómico (3/2). ¿Es NP-difícil mejorar?

• La aproximación de TSP métrico a un factor menor que 220/219 es NP-hard (Papadimitriou y Vempala, 2006 [PS] ). Que yo sepa, este es el límite inferior más conocido.

• Hay alguna evidencia que sugiere que el límite real puede ser 4/3 (Carr y Vempala, 2004 [Versión gratuita] [Buena versión] ).

• El límite superior de aproximabilidad se redujo recientemente a (Mucha 2011 "Aproximación 13/9 para TSP gráfico" [ PDF ])$13/9$

Dar una función explícita con complejidad de circuito exponencial.

Shannon demostró en 1949 que si elige una función booleana al azar, tiene una complejidad de circuito exponencial con una probabilidad de casi una.

El mejor límite inferior para una función booleana explícita que tenemos hasta ahora es por K. Iwama, O. Lachish, H Morizumi y R. Raz.5 n - o ( n $f:\{0,1\}^n \to \{0,1\}$$5n - o(n)$

¿Cuál es la complejidad de la consulta de probar la ausencia de triángulos en gráficos densos (es decir, distinguir gráficos sin triángulos de aquellos -far de ser libres de triángulos)? El límite superior conocido es una torre de exponenciales en , mientras que el límite inferior conocido es solo ligeramente polinomial en . Esta es una pregunta bastante básica en teoría gráfica extrema / combinatoria aditiva que ha estado abierta durante casi 30 años.1 / ϵ 1 /$\epsilon$$1/\epsilon$$1/\epsilon$

Separe NEXP de BPP. Las personas tienden a creer que BPP = P, pero nadie puede separar NEXP de BPP.

Sé que el OP solo solicitó un problema por publicación, pero las conferencias RTA (Técnicas de reescritura y sus aplicaciones) 1 y TLCA (Cálculos de Lambda escritos y sus aplicaciones) mantienen listas de problemas abiertos en sus campos 2 . Estas listas son bastante útiles, ya que también incluyen punteros al trabajo previo realizado para intentar resolver estos problemas.

Desrandomización del problema de prueba de identidad polinómica

El problema es el siguiente: dado un circuito aritmético que computa un polinomio , ¿ es idénticamente cero?$P$$P$

Este problema puede resolverse en tiempo polinómico aleatorio, pero no se sabe que sea solucionable en tiempo polinómico determinista.

Relacionado está la conjetura Shub y Smale . Dado un polinomio , definimos su -complejidad como el tamaño del circuito aritmético más pequeño que computa usando la única constante . Para un polinomio univariado , sea su número de raíces reales.P τ τ ( P ) P 1 P ∈ Z [ x ] z ( P $\tau$$P$$\tau$$\tau(P)$$P$$1$$P\in\mathbb Z[x]$$z(P)$

Demuestre que existe una constante universal tal que para cada , .P ∈ Z [ x ] z ( P ) ≤ ( 1 + τ ( P ) ) $c$$P\in\mathbb Z[x]$$z(P)\le (1+\tau(P))^c$

¿Existe un teorema de PCP cuántico?

Hay muchos problemas abiertos en los cálculos lambda (con y sin tipo). Vea la lista TLCA de problemas abiertos para más detalles; También hay una buena versión en PDF sin los marcos.

Particularmente me gusta el problema # 5:

¿Hay términos que no se pueden escribir en pero que se pueden escribir con ayuda de tipos recursivos positivos?$F_ω$

¿Es el problema del logaritmo discreto en P?

Deje que sea un grupo cíclico de orden y tal que es un generador de . El problema de encontrar tal que se conoce como el problema de logaritmo discreto (DLP). ¿Existe un algoritmo (clásico) para resolver el DLP en el peor tiempo de polinomio en el número de bits de ?$G$$q$$g,h \in G$$g$$G$$n \in \mathbb{N}$$g^n = h$$q$

Hay variaciones de DLP que se cree que son más fáciles, pero aún no se han resuelto. El problema computacional de Diffie-Hellman (CDH) pide encontrar dados y . El problema decisivo de Diffie-Hellman (DDH) pide decidir, dado , si .$g^{a b}$$g, g^a$$g^b$$g, g^a, g^b, h \in G$$g^{a b} = h$

Claramente, DLP es difícil si CDH es difícil, y CDH es difícil si DDH es difícil, pero no se conocen reducciones inversas, excepto en algunos grupos. La suposición de que DDH es difícil es clave para la seguridad de algunos sistemas criptográficos, como ElGamal y Cramer-Shoup .

Los juegos de paridad son juegos de gráficos de duración infinita para dos jugadores, cuyo problema de decisión natural está en NP y co-NP, y cuyo problema de búsqueda natural en PPAD y PLS.

http://en.wikipedia.org/wiki/Parity_game

¿Se pueden resolver los juegos de paridad en tiempo polinómico?

(En términos más generales, una pregunta abierta de larga data en la programación matemática es si los problemas de complementariedad lineal de la matriz P se pueden resolver en tiempo polinómico).

El área de complejidad parametrizada tiene su propia carga de problemas abiertos.

Considera los problemas de decisión

• dado ¿existe una cubierta de vértice de tamaño para el gráfico ?$(G,k)$$k$$G$
• dado ¿existe una asignación satisfactoria de peso para la fórmula ?$(F,k)$$k$$F$
• dado ¿existe una camarilla de tamaño en un gráfico ?$(G,k)$$k$$G$
• etc ...

Muchos, MUCHOS, problemas combinatorios existen en esta forma. La complejidad parametrizada considera que un algoritmo es "eficiente" si su tiempo de ejecución está limitado por donde es una función arbitraria y es una constante independiente de . En comparación, observe que todos estos problemas pueden resolverse fácilmente en .$f(k)n^c$$f$$c$$k$$n^{O(k)}$

Este marco modela los casos en los que estamos buscando una pequeña estructura combinatoria y podemos permitirnos un tiempo de ejecución exponencial con respecto al tamaño de la solución / testigo .

Un problema con dicho algoritmo (por ejemplo, cubierta de vértice) se llama Parámetro fijo manejable (FPT).

La complejidad parametrizada es una teoría madura y tiene fundamentos teóricos fuertes y atractivo para aplicaciones prácticas. Los problemas de decisión interesantes para dicha teoría forman una jerarquía de clases muy bien estructurada con problemas naturales completos:

Por supuesto, está abierto si cualquiera de estas inclusiones es estricta o no. Observe que si entonces SAT tiene un algoritmo subexponencial (esto no es trivial). La última declaración conecta la complejidad prameterizada con mencionado anteriormente.E T $FPT=W[1]$$ETH$

Observe también que investigar tales colapsos no es un ejercicio vacío: demostrar que es equivalente a demostrar que hay un algoritmo manejable de parámetros fijos para encontrar cliques.$W[1]=FPT$$k$