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

23

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δn temps pour certains δ>0 .

SETH: pour tout ε>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ε)n poly m temps.

Il est connu que SETH est plus fort que ETH et ils sont tous les deux plus forts que PNP , et tous deux plus forts que FTPW[1] .

Quatre autres conjectures importantes:

  1. Conjecture 3SUM: 3SUM sur n entiers dans {n3,,n3} nécessite n2o(1) fois

  2. Conjecture OV: Les vecteurs orthogonaux sur n vecteurs nécessitent n2o(1) temps.

  3. Conjecture APSP: toutes les paires de chemin le plus court sur n nœuds et les poids de bits O(logn) nécessitent n3o(1) temps.

  4. Conjecture BMM: Tout algorithme "combinatoire" pour la multiplication matricielle booléenne nécessite n3o(1) temps.

On sait que SETH implique la conjecture OV (Ryan Willams, 2004). Outre la preuve de Ryan que SETH 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

Rupei Xu
la source
Salut Rupei, j'ai travaillé sur divers problèmes d'accessibilité et de contraintes de graphes liés à la très belle liste de problèmes de complexité à grain fin que vous avez mentionnés. Si cela vous intéresse, envoyez-moi un e-mail et nous pourrons discuter un jour. Je suis heureux de voir d'autres personnes intéressées par la complexité à grain fin sur stackexchange. :)
Michael Wehar
3
Une réduction triviale: APSP subcubic "combinatoire" implique BMM subcubic "combinatoire". Pour 3SUM, voir la relation entre les problèmes connexes à la page 14 de cette diapositive cs.uwaterloo.ca/~tmchan/talks/bsg_stoc_talk.pdf . Pour BMM, voir la section G de cet article theory.stanford.edu/~virgi/tria-mmult-conf.pdf . Pour l'APSP, il existe de nombreux articles de Virginia montrant une équivalence sous-cubique.
Thatchaphol
1
@Thatchaphol, merci pour le genre de partage!
Rupei Xu

Réponses:

15

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.

ϵ>0kk2(1ϵ)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.

ϵ>0kk2(1ϵ)n

Rosetta
la source
1
Merci pour le travail de pionnier! Ryan Williams pense que SETH est faux. Pensez-vous que NSETH est vrai?
Rupei Xu
2
Ce document note que Ryan a réellement montré que la version MA de SETH est fausse, ce qui semble suggérer que NSETH est peu probable. Néanmoins, dans un certain sens, le fait est que, pour montrer les connexions entre certaines de ces autres conjectures, vous devez d'abord progresser sur la réfutation de NSETH.
palindrome
8

kk

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.

GMB
la source
1
Merci Greg! Ma motivation initiale de poster cette question ici est de collecter tous les résultats existants dans ce domaine, comme les bonnes collections dans The Parameterized Complexity Newsletter fpt.wikidot.com/…
Rupei Xu
k
1

O(n2ϵ)

O(n2ϵ)

kno(k)NLP

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

vzn
la source
1
Ajout de petites corrections à votre post VZN. C'était gentil de votre part de me mentionner. Je suis très passionné par le problème des intersections DFA et j'espère avoir plus de choses à partager à l'avenir. :)
Michael Wehar