Мелкозернистое сокращение

В теории сложности вычислений мелкозернистая редукция — это переход от одной вычислительной задачи к другой, используемый для связи сложности улучшения временных границ для двух задач.Интуитивно понятно, что он предоставляет метод эффективного решения одной проблемы, используя решение другой проблемы в качестве подпрограммы .Если проблема $A$ можно решить со временем $a(n)$ и проблема $B$ можно решить со временем $b(n)$, то существование $(a,b)$-уменьшение проблемы $A$ проблема $B$ подразумевает, что любое значительное ускорение решения проблемы $B$ также приведет к ускорению решения проблемы $A$.

Определение

Позволять $A$ и $B$ быть вычислительными задачами, заданными как желаемый результат для каждого возможного входа.Позволять $a$ и $b$ обе являются конструируемыми во времени функциями , принимающими целочисленный аргумент. $n$ и выдать целочисленный результат. Обычно, $a$ и $b$ являются временными рамками для известных или наивных алгоритмов решения двух задач, и часто они представляют собой мономы, такие как $n^{2}$.

Затем $A$ Говорят, что это $(a,b)$-сводимо к $B$если для каждого действительного числа $\epsilon >0$, существует действительное число $\delta >0$ и алгоритм, который решает случаи проблемы $A$ преобразуя его в последовательность примеров проблемы $B$, требуется время $O{\bigl (}a(n)^{1-\delta }{\bigr )}$ для преобразования экземпляров размера $n$и создание последовательности экземпляров, размеры которых $n_{i}$ ограничены $\sum _{i}b(n_{i})^{1-\epsilon }<a(n)^{1-\delta }$.

Ан $(a,b)$-редукция задается отображением из $\epsilon$ паре алгоритма и $\delta$.

Значение ускорения

Предполагать $A$ является $(a,b)$-сводимо к $B$, и существует $\epsilon >0$ такой, что $B$ можно решить со временем $O{\bigl (}b(n)^{1-\epsilon }{\bigr )}$.Тогда при этих предположениях существует также $\delta >0$ такой, что $A$ можно решить со временем $O{\bigl (}a(n)^{1-\delta }{\bigr )}$. А именно, пусть $\delta$ быть значением, заданным $(a,b)$- сократить и решить $A$ применив преобразование сокращения и используя быстрый алгоритм для $B$ для каждой результирующей подзадачи.

Эквивалентно, если $A$ не может быть решено во времени значительно быстрее, чем $a(n)$, затем $B$ не может быть решено во времени значительно быстрее, чем $b(n)$.

История

Были определены мелкозернистые сокращения в особом случае, когда $a$ и $b$ равные мономы, Вирджиния Василевска Уильямс и Райан Уильямс в 2010 году.Они также показали существование $(n^{3},n^{3})$-сокращение между несколькими задачами, включая поиск кратчайших путей для всех пар , поиск второго кратчайшего пути ли данная матрица расстояний между двумя заданными вершинами во взвешенном графе, поиск треугольников с отрицательным весом во взвешенных графах и проверку того, описывает метрическое пространство . Согласно их результатам, либо все эти задачи имеют временные ограничения с показателями меньше трех, либо ни одна из них не имеет ограничений по времени.

Термин «мелкозернистая редукция» возник из более поздней работы Вирджинии Василевской Уильямс в приглашенной презентации на 10-м Международном симпозиуме по параметризованным и точным вычислениям.

Хотя первоначальное определение мелкозернистых редукций включало детерминированные алгоритмы, соответствующие концепции для рандомизированных и недетерминированных алгоритмов . также рассматривались