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 .
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.
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 ] .
Otras cuatro conjeturas importantes:
Conjetura de 3SUM: 3SUM en enteros en { - n 3 , … , n 3 } requiere n 2 - o ( 1 ) tiempo
Conjetura de OV: los vectores ortogonales en vectores requieren n 2 - o ( 1 ) tiempo.
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.
Conjetura de BMM: Cualquier algoritmo "combinatorio" para la multiplicación de matrices booleanas requiere tiempo.
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
Respuestas:
Este es un documento reciente que presenta una hipótesis de tiempo exponencial fuerte no determinista (NSETH), que es una extensión de SETH.
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.
fuente
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.
fuente
La distancia de edición no se puede calcular en un tiempo fuertemente subcuadrático (a menos que SETH sea falso) / Backurs, Indyk
Un nuevo mapa traza los límites de la computación / Pavlus, revista Quanta
Durante 40 años, los informáticos buscaron una solución que no existe / Boston Globe
Evidencia desconcertante / blog RJLipton
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
fuente