Мелкозернистое измельчение

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

Пусть и будут вычислительными задачами, указанными как желаемый выход для каждого возможного входа. Пусть и обе будут функциями, конструируемыми по времени , которые принимают целочисленный аргумент и выдают целочисленный результат. Обычно и являются временными границами для известных или наивных алгоритмов для двух задач, и часто они являются мономами, такими как . ^[1]${\displaystyle А}$${\displaystyle Б}$${\displaystyle а}$${\displaystyle б}$${\displaystyle n}$${\displaystyle а}$${\displaystyle б}$${\displaystyle n^{2}}$

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

-Сокращение задается отображением из в пару алгоритма и . ^[1]${\displaystyle (а,б)}$${\displaystyle \epsilon}$${\displaystyle \дельта}$

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

Эквивалентно, если не может быть решена за время значительно быстрее, чем , то не может быть решена за время значительно быстрее, чем . ^[1]${\displaystyle А}$${\displaystyle а(н)}$${\displaystyle Б}$${\displaystyle b(n)}$

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

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

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