En märkbar bråkdel av Algoritmer papper under de senaste decennierna förbättra körtiden för välkända algoritmer för grundläggande problem av logaritmiska faktorer. Till exempel, O(n 2 ) dynamisk programmering lösning till den längsta gemensamma Subsekvens problem (LCS) förbättrades till O(n 2 / log 2 n) på flera sätt och med hjälp av en mängd olika geniala tricks. Denna forskningslinje, även känd som konsten att raka loggfaktorer, saknar ett verktyg för att bevisa negativa resultat. Närmare bestämt, hur kan vi visa att det är osannolikt att LCS kan lösas i tid O(n 2 / log 3 n)? Kanske föreslogs det enda tillvägagångssättet för sådana resultat i ett nyligen publicerat dokument av Abboud, Hansen, Vassilevska W. och Williams (STOC'16). Författarna skyller hårdheten av rakning loggar på hårdheten av att lösa tillfredsställande på booleska formler (Formula-SAT) snabbare än uttömmande sökning. De visar att en O(n 2 / log 1000 n) algoritm för LCS skulle innebära ett stort framsteg i kretsen lägre gränser. Huruvida detta tillvägagångssätt kan leda till strängare hinder var oklart. I detta dokument driver vi denna strategi till sin gräns och i synnerhet bevisar att ett välkänt hinder från komplexitetsteorin står i vägen för att ytterligare fem logfaktorer för grundläggande kombinatoriska problem ska kunna rakas. För LCS, regelbunden uttrycksmönster matchning, liksom Fréchet avståndsproblem från beräkningsgeometri, visar vi att en O(n 2 / log 7+ε n) körtid skulle innebära nya formel-SAT algoritmer. Vårt huvudsakliga resultat är en minskning från SAT på formler av storlek s över n variabler till LCS på sekvenser av längd N = 2 n/2 · s 1+o(1). Vår minskning är i huvudsak så effektiv som möjligt, och det förbättrar avsevärt den tidigare kända minskningen för LCS med N = 2 n/2 · s c, för vissa c ≥ 100.
Deras minskning stramas senare av Abboud och Bringmann REF, som visade att en n 2 / log 7+ε n tid algoritm för någon av dem är redan tillräckligt för att innebära ny algoritm för formel-SAT.
Tighter Connections Between Formula-SAT and Shaving Logs
{'venue': 'ICALP', 'journal': None, 'mag_field_of_study': ['Computer Science']}