Redigeringsavståndet (alias Levenshtein-avståndet) mellan två strängar definieras som minsta antal tillägg, raderingar eller substitutioner av symboler som behövs för att omvandla en sträng till en annan. Problemet med att beräkna redigeringsavståndet mellan två strängar är en klassisk beräkningsuppgift, med en välkänd algoritm baserad på dynamisk programmering. Tyvärr, alla kända algoritmer för detta problem körs i nästan kvadratisk tid. I detta dokument ger vi bevis för att de nära-kvadratiska körtidsgränser som är kända för problemet med datorredigering avstånd kan vara snäv. Specifikt visar vi att om redigeringsavståndet kan beräknas i tid O(n 2−δ ) för vissa konstant δ > 0, då tillfredsställelsen av konjunktiva normala formformler med N variabler och M klausuler kan lösas i tid M O(1) 2 (1− )N för en konstant > 0. Det senare resultatet skulle bryta mot Strong Exponential Time Hypotes, som postulerar att sådana algoritmer inte finns.
För tidsgränser visar Backurs och Indyk REF att den starka Exponential Time Hypotesen innebär att den allmänna redigeringen av avståndsproblem inte kan lösas i tid bättre än n 2".
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
{'venue': "STOC '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}