Under de senaste åren har betydande framsteg gjorts när det gäller att förklara den uppenbara hårdheten i att förbättra de naiva lösningarna för många grundläggande polynomiskt lösliga problem. Dessa framsteg har skett i form av villkorade minskningar av de lägre gränserna från ett problem som antas vara svårt. De svåra problemen inkluderar 3SUM, All-Pairs Shortest Path, SAT, Orthogonal Vectors, och andra. I (min, +)-konvolution problem, är målet att beräkna en sekvens (c. Detta kan enkelt göras i O(n 2 ) tid, men ingen O(n 2−ε ) algoritm är känd för ε > 0. I den här artikeln genomför vi en systematisk studie av (min, +)konvolutionsproblem som ett hårdhetsantagande. För det första etablerar vi likvärdigheten av detta problem till en grupp av andra problem, inklusive varianter av den klassiska knapsack problem och problem relaterade till subadditiva sekvenser. Problemet (min, +)-konvolution har använts som en byggsten i algoritmer för många problem, särskilt problem inom strängologi. Det har också framträtt som en ad hoc hårdhet antagande. För det andra undersöker vi några av dessa förbindelser och ger nya minskningar och andra resultat. Vi förklarar också varför det kanske inte är möjligt att ersätta detta antagande med Strong Exponential Time Hypotes för vissa problem.
I REF presenterar författarna en ekvivalensklass för (min, +)-konvolution, inklusive några varianter av den klassiska knapsack problem och problem relaterade till subadditiva sekvenser.
On Problems Equivalent to (min,+)-Convolution
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}