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

218

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

¿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.
Shane
fuente
1
Como está solicitando una lista y no hay una respuesta única, esto puede funcionar mejor marcado como un wiki de la comunidad.
Daniel Apon
2
Un problema no resuelto por respuesta, por favor; ¡entonces podemos clasificar fácilmente las respuestas votando arriba / abajo!
Jukka Suomela
15
¿Por qué solo resulta la complejidad? ¡Hay más en TCS que complejidad! ¿No hay problemas abiertos en la teoría de tipos? ¿lenguajes de programación?
Jacques Carette
3
agrégalos, Jacques :).
Suresh Venkat
8
Creo que deberíamos distinguir entre los principales problemas abiertos que se consideran problemas fundamentales , como , y los principales problemas abiertos que, si se resuelven, constituirán un avance técnico, pero no son necesariamente tan fundamentales, por ejemplo, límites inferiores exponenciales en circuitos (es decir, puertas). Por lo tanto, posiblemente deberíamos abrir una nueva wiki de la comunidad titulada "problemas abiertos en las fronteras de TCS", o similares. A C 0 ( 6 ) A C 0 +PNPAC0(6)AC0+mod6
Iddo Tzameret

Respuestas:

137

¿Se puede multiplicar por matrices en operaciones ?n O ( n 2 )nnO(n2)

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.ωωω

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.ω < 2.372873ω<2.3737ω<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 ).ω<2.3728639

András Salamon
fuente
¿Qué tal un objetivo modesto y realista de o alguna otra función entre y ? Después de todo, se espera que la multiplicación entera tenga el límite inferior de . n 2 + ϵ n 2 O ( n log n )O(n2logn)n2+ϵn2O(nlogn)
Mitch
No estoy seguro de que pasar de a se considere como un "objetivo modesto y realista", y mucho menos ir por debajo de . Pero sería genial ver algún progreso, ¡así que pruébalo! 2 + ϵ 2 + ϵ2+0.3762+ϵ2+ϵ
András Salamon
13
El exponente de multiplicación matricial se define como el número real más pequeño modo que las operaciones aritméticas suficientes para todos . Probablemente debería esperarse un factor como . O ( n ω + ϵ ) ϵ > 0 log nωO(nω+ϵ)ϵ>0logn
Zeyu
2
Simplemente añadiendo en aras de la exhaustividad, el conocimiento actual de que CW obligado fue mejorado hace unos días por Virginia Williams. Y como lo han señalado muchos otros en la comunidad, Andrew Stothers había obtenido su CW vencido alrededor de un año antes de Virginia. El registro actual esO(n2.373)
Akash Kumar
123

¿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.

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 .

András Salamon
fuente
Por favor, eche un vistazo a esta entrada también.
MS Dousti
Arranqué un límite inferior exacto para la detección genérica de automorfismo de fuerza bruta. oeis.org/A186202 Mucho menos quepero aun exponencial. Esperando que McKay lo acople a los Schrier-Sims para su última encarnación de NAUTY para que funcione en hardware paralelo. n!
Chad Brewbaker
1
Babai se retractó del reclamo de tiempo de ejecución cuasipolinomial . Aparentemente hubo un error en el análisis.
Raphael
44
El reclamo fue restaurado: people.cs.uchicago.edu/~laci/update.html
citando el
91

Complejidad de Factoring

¿Está factorizando en ?P

Kaveh
fuente
¿Alguna buena publicación que conozca que describa la complejidad de las pruebas de factorización o primalidad en términos de la estructura del semigrupo de transformaciones de suma y multiplicación en Z_n? Por ejemplo, en [0,1,2] es la transformación +0 | x1, [1,2,0] es la transformación +1 ...Z3
Chad Brewbaker
66

¿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?

Jɛ ff E
fuente
11
Agregaré a esta pregunta: ¿mostrar la inexistencia de LP fuertemente polinomial implicaría algún resultado de separación de clases?
Anand Kulkarni
,,, y la conjetura de Hirsch ...
Sariel Har-Peled
77
En 2011, Oliver Friedmann mostró límites inferiores exponenciales para muchas reglas pivotantes (en realidad afirma "esencialmente todas las reglas pivotantes naturales", incluidas Random Facet y Random Edge). Estos límites se aplican al resolver un programa lineal derivado de juegos de paridad de 2 jugadores. La tesis de Friedmann edoc.ub.uni-muenchen.de/13294 examina la historia con cierta profundidad (incluidas varias formas de la Conjetura de Hirsch y el contraejemplo de 2010 a la forma fuerte de Francisco Santos).
András Salamon
63

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.

András Salamon
fuente
44
En serio, no llamaría al ETH un problema abierto importante en este momento exactamente porque implica P ≠ NP y, por lo tanto, es al menos tan difícil de probar.
Holger
17
¿No? En mi humilde opinión, su argumento implica que ETH es aún más un gran problema abierto que PvsNP.
Jeff el
¿Podría explicar por qué no implica el ETH? PNP
Emil
13
Si , entonces , pero ETH es falso. P N PNP=PTIME(nlogn)PNP
Jeffε
3
Ah ok ¿Pero te refieres a DTIME ( )? nlogn
Emil
59

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.PNP

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.

Holger
fuente
3
Immerman-Vardi muestra que la lógica de captura FO (LFP) en estructuras <i> ordenadas </i>, por lo que esta es una pregunta sobre la captura de PTIME en modelos arbitrarios finitos, supongo. Si te entiendo correctamente, ¿no es esta pregunta una traducción de preguntar si P! = NP? Podría ser más conveniente preguntar uno o más de los problemas abiertos en la encuesta a la que se vincula. Disculpas si estoy siendo despistado aquí.
Aaron Sterling el
55
Gracias, edité la respuesta para mencionar a Immerman-Vardi para aclaraciones. No, no se sabe que este problema abierto sea equivalente a P vs NP. Los problemas abiertos en la encuesta son casos especiales del gran problema abierto y no son apropiados en este hilo. Quizás esta referencia también sea útil: rjlipton.wordpress.com/2010/04/05/…
Holger
55

¿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?

Anand Kulkarni
fuente
¿No sería más preciso decir que si el UGC no es cierto (es decir, los juegos únicos no son NP-hard, solo más difíciles que P), ¿dónde encajaría UGC en el paisaje?
András Salamon
Ups Sí, debería reformular esto. Mi intención era resaltar la aparente discrepancia que resulta de los juegos únicos que tienen un algoritmo de aproximación no trivial en un tiempo sub-exponencial (pero no del todo polinomial). Más de: ¿Qué dice esto, si el tiempo de ejecución sub-exponencial es óptimo para juegos únicos?
Daniel Apon
2
En retrospectiva, pensé que debería incluir un puntero hacia esta preimpresión . En mi opinión, es un desarrollo tan grande como el documento que he vinculado en la respuesta.
Daniel Apon el
1
Vale la pena señalar que no se conocen instancias difíciles de UCG. El mejor enfoque actual funciona de manera eficiente en todos los casos probados. Simplemente no podemos probar que hemos encontrado los ejemplos más patológicos.
Stella Biderman
55

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.

Kaveh
fuente
55
Para mí, esto no califica como un "gran problema abierto", porque la pregunta teórica de la complejidad real (tienen diferentes complejidades) está subsumida por P = NP (ya que #P es un superconjunto de NP) y con esa pregunta a un lado No hay un problema concreto planteado aquí.
David Eppstein
De hecho, estoy de acuerdo con esto.
Ross Snider, el
10
@DavidEppstein: Per v. Det está más cerca de GapP v GapL, un análogo de conteo de NP v NL. Es posible que y, por tanto, . Además, por v det es mucho más antiguo que P v NP, esencialmente volviendo a [Polya 1913], en el que muestra que no se pueden colocar signos en una matriz para cambiar su permanente a su determinante (excepto 2x2). Valiant introdujo una variante en esas preguntas (permitiendo que el tamaño de det sea mayor que n) debido a su importancia en la complejidad, pero incluso los trabajos anteriores a Valiant dan la motivación "porque lo permanente es muy difícil de calcular ..." (por ejemplo Gibson 1971)G a p P G a p LNLP=NPGapPGapL
Joshua Grochow
¿Cuáles son los algoritmos de última generación para calcular el permanente de una matriz 0-1? es decir, el número de matrices de permutación legales que puede generar a partir de un subconjunto de los 1.
Chad Brewbaker
@ChadBrewbaker: ver Mark Jerrum, Alistair Sinclair, Eric Vigoda, "Algoritmo de aproximación de tiempo polinómico para el permanente de una matriz con entradas no negativas", Journal of the ACM 51/4 (2004), 671, citeseerx.ist. psu.edu/viewdoc/summary?doi=10.1.1.141.116
Zsbán Ambrus
47

¿Podemos calcular la FFT en mucho menos tiempo que ?O(nlogn)

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(n3ϵ)

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(n32Ω(logn)1/2)

Alex Andoni
fuente
3
Un desarrollo interesante sobre FFT: "* Un algoritmo de tiempo O (k log n) para el caso donde la señal de entrada tiene como máximo k coeficientes de Fourier distintos de cero, y * An O (k log n log (n / k)) algoritmo de tiempo para señales de entrada generales ". fuente: arxiv.org/abs/1201.2501v1
Shadok
44

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.

Ross Snider
fuente
77
Esto también está relacionado con la complejidad de la prueba proposicional. Existe un sistema de prueba proposicional polinomial si es igual a . NPcoNP
Kaveh
41

¿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.

András Salamon
fuente
16
Estoy bastante seguro de que los algoritmos LP, tal como están hoy, no son paralelizables. Creo que encajan en el modelo de operaciones RAM sin bit de Mulmuley. En dx.doi.org/10.1137/S0097539794282930 K. Mulmuley. Límites inferiores en un modelo paralelo sin operaciones de bits. SIAM J. Comput. 28 (4), 1460-1509 (1999) muestra que en ese modelo, mostrando que muchos algoritmos naturales (generalmente numéricos) para problemas completos no son paralelizables. Esto no responde a la pregunta en el caso booleano, pero sí responde a una gran clase de algoritmos naturales. PNCP
Joshua Grochow
41

¿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 ).(Fn)n=1pFnp(|Fn|)n=1,2,|Fn|Fn


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 A0(x¯),,Ak(x¯)k0A1(x¯),,Ak(x¯)A0(x¯)k=0F0F1,,FkF0,,FkA1,,Akx¯B1,,Bn 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 .Fi=Ai(B1/x1,,Bn/xn),i=0,,kA1,,AkA0

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.AA

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).TTFFTT

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.PPP

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.NPcoNP

Iddo Tzameret
fuente
38

¿Podemos calcular la distancia de edición entre dos cadenas de longitud en tiempo subcuadrático, es decir, en el tiempo para algún ?nO(n2ϵ)ϵ>0

Piotr
fuente
8
¿Tienes referencias para eso? De hecho, pensé que esta proposición era trivialmente falsa, aunque no puedo pensar en una prueba fuera de mi cabeza. (Aunque sé que el tiempo de ejecución puede depender de la cantidad de errores).
Konrad Rudolph,
55
Actualización (STOC 2015): Backurs e Indyk dan evidencia de que no es posible un tiempo mejor que el cuadrático. Ver rjlipton.wordpress.com/2015/06/01/puzzling-evidence .
Neal Young el
38

¿Existen realmente algoritmos de tiempo subcuadrático (es decir, tiempo para algunos constantes para problemas difíciles de 3SUM ?O(n2δ)δ>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(n2/(logn/loglogn)2/3)O(n2)

Aryabhata
fuente
99
Buena pregunta. Sin embargo, la existencia de algoritmos subcuadráticos para el problema 3SUM está abierta incluso para algoritmos aleatorios . Por supuesto, el algoritmo determinista hubiera sido aún mejor ...
Piotr
3
En el caso cuántico, se conocen n log (n) límites inferiores y superiores coincidentes para 3SUM: Andrej Dubrovsky, Oksana Scegulnaja-Dubrovska Límites inferiores cuánticos mejorados para el problema de 3 sumas. Actas de Baltic DB&IS 2004, vol. 2, Riga, Letonia, págs. 40-45.
Martin Schwarz el
1
Tenía la impresión de que no tenemos n ^ 2 límite inferior para ningún problema en NP.
Sariel Har-Peled
1
Tuve la clara impresión de que si está restringido a problemas de decisión (sin argumentos de salida), entonces no se sabe nada. Pero realmente deberías preguntarle a una persona compleja.
Sariel Har-Peled
3
Un artículo reciente de arXiv afirma haber resuelto esta conjetura al proporcionar algoritmos subcuadráticos para 3-SUM.
Mangara
35

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.

Joe Fitzsimons
fuente
33
  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?

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

  4. ¿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.)

Aaron Sterling
fuente
¿Es esto lo mismo que p-measure en el Complexity Zoo? ¿A dónde iría para leer más al respecto?
András Salamon
2
La medida P es un ejemplo de medida limitada por recursos: en términos más generales, puede imaginarse una máquina tratando de predecir una secuencia, y los recursos computacionales que tiene disponibles para hacerlo son los que proporcionan el límite de recursos en la medida. Utilicé p-measure en mi explicación informal de EXP en una mesa. Para leer más, recomiendo la versión del diario de la siguiente encuesta realizada por Lutz (la CZ cita la versión de la conferencia de esta encuesta). cs.iastate.edu/~lutz/=PAPERS/qset.ps (en postscript, espero que esté bien)
Aaron Sterling
Gracias. Aquí hay un PDF de ese documento para aquellos que no pueden leer PS: archives.cs.iastate.edu/documents/disk0/00/00/01/28/00000128-01/…
András Salamon
2
Sí a tu primera pregunta. P tiene la medida 0 en EXP, por lo que si NP no, obtienes P! = NP inmediatamente. Para la segunda pregunta, le sugiero que lea el último párrafo de la página 28 de la encuesta a la que Andras y yo nos vinculamos. (No hay suficiente espacio en el comentario para pegarlo aquí, lo siento). Básicamente, si NP tiene la medida cero, existe un algoritmo factible que podría adivinar bien la pertenencia a un problema difícil de NP. Por lo tanto, parece probable que NP no sea cero en EXP.
Aaron Sterling el
1
@Artem: puedes comenzar aquí: blog.computationalcomplexity.org/2003/03/…
Aaron Sterling
29

¿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

James King
fuente
1
TSP métrico realizado recientemente por 3/2 - e donde e es constante (cerca de 0.002)
Saeed
1
alguna discusión sobre TSP métrico en la carta perdida de Godel
Artem Kaznatcheev
2
@Saeed, ¿te referías al algoritmo solo para el caso especial de Metric TSP: para Graphic TSP? Luego fue mejorado a 13/9 por Mucha. Parece que 3/2 es el límite superior más conocido para TSP métrico.
Alex Golovnev
@AlexGolovnev, Hola Alex, Sí, pero mi comentario fue antes de que llegara el nuevo periódico;) (Vi el papel de Oveis Gharan en ese momento).
Saeed
28

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{0,1}5no(n)

Kaveh
fuente
11
Esta forma de señalar el problema siempre me molesta, porque debes tener cuidado con lo que quieres decir con "explícito". Es fácil escribir una descripción de una función que tiene una complejidad de circuito exponencial. Si "explícito" significa "computable en tiempo exponencial o menos", entonces estoy de acuerdo, este es un gran problema abierto.
Ryan Williams el
1
Ryan, tienes razón. Este es un punto extremadamente importante. También es fácil escribir una descripción de una función no calificable. En el artículo que cito, se prueba el límite inferior para una función que es construible en tiempo polinómico determinista.
Marc
¿Hay una buena exposición sobre el trabajo de Shannon?
T ....
3
El argumento se detalla en las siguientes notas de clase: math.tau.ac.il/~zwick/scribe-boolean.html
Marc
Este es un problema excelente y me trae buenos recuerdos de que me asignaron el resultado de Shanon en mi segundo año de universidad.
Stella Biderman
27

¿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 / ϵϵ1/ϵ1/ϵ

revs arnab
fuente
27

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

Bin Fu
fuente
26

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.

Dominic Mulligan
fuente
1
No hay problema. ¿Alguien sabe de otras listas similares de otras conferencias? Son bastante interesantes de leer.
Dominic Mulligan
26

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?PPP

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 )τPττ(P)P1PZ[x]z(P)

Demuestre que existe una constante universal tal que para cada , .P Z [ x ] z ( P ) ( 1 + τ ( P ) ) ccPZ[x]z(P)(1+τ(P))c

Bruno
fuente
25

¿Existe un teorema de PCP cuántico?

Robin Kothari
fuente
Esta pregunta fue mencionada en el blog de Scott Aaronson hace un tiempo scottaaronson.com/blog/?p=139 pero no sé si ha habido algún progreso desde entonces.
Anthony Leverrier
Creo que esta respuesta necesita ser actualizada.
Kaveh
@Kaveh: ¿Qué te gustaría ver agregado?
Robin Kothari
25

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ω

Jacques Carette
fuente
3
Gracias a Dominic Mulligan por señalarme a esta lista particular de problemas.
Jacques Carette
25

¿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 ?Gqg,hGgGnNgn=hq

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 .gabg,gagbg,ga,gb,hGgab=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 .

Felipe Lacerda
fuente
3
Bueno, sabemos que DLP está contenido en BQP.
Joe Fitzsimons
DLP se puso recientemente en cuasi-P para el grupoG=Fpn×
Marque el
24

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).

Rahul Savani
fuente
23

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)kG
  • dado ¿existe una asignación satisfactoria de peso para la fórmula ?(F,k)kF
  • dado ¿existe una camarilla de tamaño en un gráfico ?(G,k)kG
  • 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)ncfcknO(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:

FPTW[1]W[2]W[i]W[i+1]W[P]

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 HFPT=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.kW[1]=FPTk

MassimoLauria
fuente