Ett centralt problem i parameteriserade algoritmer är att erhålla algoritmer med körtid f (k) · n O(1) så att f är så långsamt växande funktion av parametern k som möjligt. I synnerhet ett stort antal grundläggande parameteriserade problem erkänna parameteriserade algoritmer där f (k) är en-exponentiell, det vill säga c k för vissa konstant c, vilket gör att sikta på en sådan löptid ett naturligt mål för andra problem också. Men det finns fortfarande gott om problem där f (k) visas i den mest kända körtiden är värre än en-exponentiell och det förblev "lätt superexponentiell" även efter allvarliga försök att få ner den. En naturlig fråga att ställa är om f (k) som visas i körtiden för de mest kända algoritmer är optimal för något av dessa problem. I detta dokument undersöker vi parameteriserade problem där vi i den mest kända körtiden och för ett antal sådana problem visar att beroendet av k i körtiden inte kan förbättras till enstaka exponentiellt. Mer exakt visar vi följande snäva nedre gränser, för fyra naturliga problem, som uppstår från tre olika områden: • I den närmaste sträng problem, givna strängar s 1,. .., s t över ett alfabet  på längden L varje, och ett heltal d, är frågan om det finns en sträng s över  på längden L, sådan att dess hamming avstånd från var och en av strängarna s i, 1 ≤ i ≤ t, är som mest d. Mönstret matchande problem Closest String är känd för att vara lösbar i tid 2 1) tid algoritmer, om inte Exponential Time Hypothesis (ETH) misslyckas. • Grafen inbäddar problem Distortion, det vill säga att avgöra om en graf G har en metrisk inbäddning i heltal med distorsion som mest d kan lösas i tid 2 1) tid algoritm, om ETH misslyckas. • Problemet med delade vägar kan lösas i tid 2 O(w log w) · n O(1) på grafer av trädbredd som mest w. Vi visar att det inte finns någon 2 o(w log w) · n O(1) tid algoritm, om inte ETH misslyckas. • Det kromatiska talet problemet kan lösas i tid 2 O(w log w) · n på grafer av trädbredd som mest w. Vi visar att det inte finns 2 o(w log w) · n O(1) tid algoritm, om ETH misslyckas. För att få våra resultat, visar vi först den nedre gränsen för varianter av grundläggande problem: hitta kliquer, oberoende uppsättningar, och slå uppsättningar. Dessa artificiellt begränsade varianter utgör en bra utgångspunkt för att bevisa lägre gränser på naturliga problem utan några * En preliminär version av papperet dök upp i förfarandet vid SODA 2011. tekniska begränsningar och kan vara av oberoende intresse. Flera uppföljningsarbeten har redan fått snäva nedre gränser genom att använda vårt ramverk, och vi tror att det kommer att visa sig vara användbart för att få ännu lägre gränser i framtiden.
En nästan matchande lägre gräns på löptiden (förutsatt ETH) erhölls av Lokshtanov et al. Hoppa över det.
Slightly Superexponential Parameterized Problems
{'venue': 'SIAM Journal on Computing, 2018', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}