¿Cuáles son las relaciones entre esas hipótesis en la teoría de la complejidad de grano fino?

23

La teoría de la complejidad, a través de conceptos como la completitud de NP, distingue entre problemas computacionales que tienen soluciones relativamente eficientes y aquellos que son intratables. La complejidad "de grano fino" tiene como objetivo refinar esta distinción cualitativa en una guía cuantitativa en cuanto al tiempo exacto requerido para resolver problemas. Más detalles se pueden encontrar aquí: http://simons.berkeley.edu/programs/complexity2015

Aquí hay algunas hipótesis importantes:

ETH: - S A T requiere 2 δ n tiempo para algunos δ > 0 .3SAT2δnδ>0

SETH: por cada , hay una k tal que k - S A T en n variables, las cláusulas m no se pueden resolver en 2 ( 1 - ε ) n p o l y m time.ε>0kkSATnm2(1ε)n poly m

Se sabe que SETH es más fuerte que ETH y ambos son más fuertes que , y ambos más fuertes que F T P W [ 1 ] .PNPFTPW[1]

Otras cuatro conjeturas importantes:

  1. Conjetura de 3SUM: 3SUM en enteros en { - n 3 , , n 3 } requiere n 2 - o ( 1 ) tiempon{n3,,n3}n2o(1)

  2. Conjetura de OV: los vectores ortogonales en vectores requieren n 2 - o ( 1 ) tiempo.nn2o(1)

  3. Conjetura de APSP: la ruta más corta de todos los pares en nodos y pesos de bit O ( log n ) requiere n 3 - o ( 1 ) tiempo.nO(logn)n3o(1)

  4. Conjetura de BMM: Cualquier algoritmo "combinatorio" para la multiplicación de matrices booleanas requiere tiempo.n3o(1)

Se sabe que SETH implica la conjetura del VO (Ryan Willams, 2004). Además de la prueba de Ryan de que SETH OV Conjetura, no hay otras reducciones relacionadas con las conjeturas conocidas.

Mi pregunta: ¿Conoces otras hipótesis o conjeturas relacionadas en esta área? ¿Cuáles son las relaciones entre ellos?

Reconocimiento: los resultados enumerados son de las diapositivas de Virginia Vassilevska Williams, ella también me dio respuestas parciales a esta pregunta.

Enlace a diapositivas: http://theory.stanford.edu/~virgi/overview.pdf

Rupei Xu
fuente
Hola Rupei, he estado trabajando en varios problemas de alcance y restricción de gráficos que están relacionados con la muy buena lista de problemas de complejidad de grano fino que mencionaste. Si está interesado, envíeme un correo electrónico y podríamos chatear en algún momento. Me alegra ver a otros interesados ​​en la complejidad de grano fino en stackexchange. :)
Michael Wehar
3
Una reducción trivial: la APSP subcúbica "combinatoria" implica BMM subcúbica "combinatoria". Para 3SUM, vea la relación entre los problemas relacionados en la página 14 de esta diapositiva cs.uwaterloo.ca/~tmchan/talks/bsg_stoc_talk.pdf . Para BMM, consulte la Sección G de este artículo theory.stanford.edu/~virgi/tria-mmult-conf.pdf . Para APSP, hay muchos documentos de Virginia que muestran equivalencia subcúbica.
Thatchaphol
1
@ Thatchaphol, ¡Gracias por el amable intercambio!
Rupei Xu

Respuestas:

15

Este es un documento reciente que presenta una hipótesis de tiempo exponencial fuerte no determinista (NSETH), que es una extensión de SETH.

ϵ>0kk2(1ϵ)n

NSETH implica SETH. Si NSETH es verdadero, entonces algunos problemas no tienen límites inferiores SETH (porque tienen algoritmos no deterministas más rápidos que los algoritmos deterministas).

Este artículo también introdujo la hipótesis de tiempo exponencial fuerte no uniforme no uniforme (NUNSETH), una hipótesis más fuerte que NSETH y SETH.

ϵ>0kk2(1ϵ)n

Rosetta
fuente
1
¡Gracias por el trabajo pionero! Ryan Williams cree que SETH es falso. ¿Crees que NSETH es cierto?
Rupei Xu
2
Este documento señala que Ryan realmente ha demostrado que la versión MA de SETH es falsa, lo que parece sugerir que es poco probable que NSETH sea cierta. Sin embargo, en cierto sentido, el punto es que, para mostrar las conexiones entre algunas de estas otras conjeturas, primero debe avanzar en la refutación de NSETH.
palíndromo el
8

kk

Este no es exactamente el tipo de relación que está buscando, pero hubo un documento interesante de FOCS que muestra que un problema natural llamado "Triángulos coincidentes" es difícil bajo cualquiera de las conjeturas SETH, 3SUM o APSP (ver aquí ). Actualmente no se sabe si alguna de estas tres conjeturas se implican entre sí de alguna manera interesante: esta es una de las principales preguntas abiertas de Complejidad de grano fino.

GMB
fuente
1
Gracias Greg! Mi motivación original para publicar esta pregunta aquí es recopilar todos los resultados existentes en esta área, como las buenas colecciones en The Parameterized Complexity Newsletter fpt.wikidot.com/…
Rupei Xu
k
1

O(n2ϵ)

O(n2ϵ)

kno(k)NLP

en este sentido también vale la pena mencionar que existe una conexión significativa conocida entre las construcciones de DFA y los cálculos de distancia de Levenshtein, por ejemplo, en este documento

vzn
fuente
1
Se agregaron algunas pequeñas correcciones a su publicación VZN. Fue amable de tu parte mencionarme. Me apasiona el problema de la intersección de DFA y espero tener más cosas para compartir en el futuro. :)
Michael Wehar