Quelles sont les relations entre ces hypothèses dans la théorie de la complexité à grain fin?

La théorie de la complexité, à travers des concepts tels que la complétude NP, fait la distinction entre les problèmes de calcul qui ont des solutions relativement efficaces et ceux qui sont insolubles. La complexité "fine" vise à affiner cette distinction qualitative en un guide quantitatif quant au temps exact requis pour résoudre les problèmes. Plus de détails peuvent être trouvés ici: http://simons.berkeley.edu/programs/complexity2015

Voici quelques hypothèses importantes:

ETH: $3$ - $SAT$ nécessite $2^{\delta n}$ temps pour certains $\delta > 0$ .

SETH: pour tout $\varepsilon > 0$ , il y a un $k$ tel que $k$ - $SAT$ sur $n$ variables, les clauses $m$ ne peuvent pas être résolues en $2^{(1-\varepsilon)n}~poly~m$ temps.

Il est connu que SETH est plus fort que ETH et ils sont tous les deux plus forts que $P \neq NP$ , et tous deux plus forts que $FTP\neq W[1]$ .

Quatre autres conjectures importantes:

1. Conjecture 3SUM: 3SUM sur $n$ entiers dans $\{-n^3,…,n^3\}$ nécessite $n^{2-o(1)}$ fois

2. Conjecture OV: Les vecteurs orthogonaux sur $n$ vecteurs nécessitent $n^{2-o(1)}$ temps.

3. Conjecture APSP: toutes les paires de chemin le plus court sur $n$ nœuds et les poids de bits $O(\log n)$ nécessitent $n^{3-o(1)}$ temps.

4. Conjecture BMM: Tout algorithme "combinatoire" pour la multiplication matricielle booléenne nécessite $n^{3-o(1)}$ temps.

On sait que SETH implique la conjecture OV (Ryan Willams, 2004). Outre la preuve de Ryan que SETH$\implies$ OV Conjecture, il n'y a pas d'autres réductions concernant les conjectures connues.

Ma question: connaissez-vous d'autres hypothèses ou conjectures connexes dans ce domaine? Quelles sont les relations entre eux?

Remerciements: les résultats énumérés proviennent des diapositives de Virginia Vassilevska Williams, elle m'a également donné des réponses partielles à cette question.

Lien vers les diapositives: http://theory.stanford.edu/~virgi/overview.pdf

Il s'agit d'un article récent présentant l'hypothèse de temps exponentiel fort non déterministe (NSETH), qui est une extension de SETH.

$\epsilon >0$$k$$k$$2^{(1-\epsilon)n}$

NSETH implique SETH. Si NSETH est vrai, certains problèmes n'ont pas de bornes inférieures SETH (car ils ont des algorithmes non déterministes plus rapidement que les algorithmes déterministes).

Cet article a également présenté l'hypothèse de temps exponentiel fort non déterministe non uniforme (NUNSETH), une hypothèse plus forte que NSETH et SETH.

$\epsilon >0$$k$$k$$2^{(1-\epsilon)n}$

$k$$k$

Ce n'est pas exactement le type de relation que vous recherchez, mais il y avait un article FOCS intéressant montrant qu'un problème naturel appelé "Matching Triangles" est difficile sous l' une des conjectures SETH, 3SUM ou APSP (voir ici ). On ne sait pas actuellement si l'une ou l'autre de ces trois conjectures s'implique de manière intéressante - c'est l'une des principales questions ouvertes de la complexité à grain fin.

$O(n^{2-\epsilon})$

• La distance d'édition ne peut pas être calculée en temps fortement sous-quadratique (sauf si SETH est faux) / Backurs, Indyk

• Une nouvelle carte trace les limites du calcul / Pavlus, Quanta magazine

• Depuis 40 ans, les informaticiens recherchent une solution qui n'existe pas / Boston Globe

• Puzzling Evidence / Blog RJLipton

$O(n^{2-\epsilon})$

• Décider de la vacuité de l'intersection des langages réguliers en temps sub-quadratique / théorie des SE

$k$$n^{o(k)}$$NL \subsetneq P$

• Résultats de dureté pour non-vide d'intersection / Wehar

dans ce sens, il convient également de mentionner qu'il existe un lien significatif connu entre les constructions DFA et les calculs de distance de Levenshtein, par exemple dans cet article

• Correction rapide des cordes avec les automates Levenshtein / Shulz, Mihov