Klassiska likhetsmått på strängar är den längsta vanliga subsekvensen och Levenshtein avstånd (dvs. det klassiska redigeringsavståndet). Ett klassiskt likhetsmått på kurvor är dynamisk tidsförvrängning. Dessa åtgärder kan beräknas av enkla O(n 2 ) dynamiska programmeringsalgoritmer, och trots mycket ansträngning inga algoritmer med betydligt bättre körtid är kända. Vi bevisar att, även begränsad till binära strängar eller endimensionella kurvor, dessa åtgärder inte har starkt subquadratiska tid algoritmer, dvs inga algoritmer med körtid O(n 2−ε ) för någon ε > 0, om inte Strong Exponential Time Hypothesis misslyckas. Vi generaliserar resultatet för att redigera avstånd för godtyckliga fasta kostnader för de fyra operationerna (deletion i en av de två strängarna, matchning, substitution), genom att identifiera triviala fall som kan lösas i konstant tid, och bevisa quadratic-time hårdhet på binära strängar för alla andra kostnadsval. Detta förbättrar och generaliserar den kända hårdheten resultat för Levenshtein avstånd [Backurs, Indyk STOC'15] genom begränsningen till binära strängar och generaliseringen till godtyckliga kostnader, och lägger till viktiga problem till en ny rad forskning som visar villkorade lägre gränser för ett växande antal kvadratiska tidsproblem. Som vårt viktigaste tekniska bidrag inför vi en ram för att bevisa fyrfaldiga tidshårdhet hos likhetsåtgärder. För att tillämpa ramen räcker det att konstruera en enda prylar, som inkapslar all den uttryckskraft som krävs för att emulera en minskning från tillfredsställande. Slutligen bevisar vi quadratic-time hårdhet för längsta palindromic subsequence och längsta tandem subsequence via minskningar från längsta gemensamma subsequence, visar att villkorade lägre gränser baserat på den starka Exponential Time Hypothesis också gäller strängproblem som inte nödvändigtvis likhet åtgärder.
Bringmann och Künnemann REF visade sig ha lägre gränser för dynamisk tidsförvrängning och längsta gemensamma undersekvens.
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
{'venue': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'journal': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}