Мелкозернистое сокращение - Fine-grained reduction

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

Определение

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

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

An ${ Displaystyle (а, б)}$ -редукция задается отображением из ${ displaystyle epsilon}$ к паре алгоритма и ${ displaystyle delta}$ .^[1]

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

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

Эквивалентно, если ${ displaystyle A}$ не может быть решена во времени значительно быстрее, чем ${ Displaystyle а (п)}$ , тогда ${ displaystyle B}$ не может быть решена во времени значительно быстрее, чем ${ Displaystyle б (п)}$ .^[1]

История

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

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

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

использованная литература

^ ^а ^б ^c ^d ^е ^ж Уильямс, Вирджиния В. (2015), «Трудность простых задач: твердость основывается на популярных гипотезах, таких как сильная гипотеза экспоненциального времени», 10-й Международный симпозиум по параметризованным и точным вычислениям, LIPIcs. Leibniz Int. Proc. Сообщить., 43, Schloss Dagstuhl. Лейбниц-Цент. Информ., Вадерн, стр. 17–29, Г-Н 3452406
^ Уильямс, Вирджиния Василевска; Уильямс, Р. Райан (2018), «Субкубические эквивалентности между задачами пути, матрицы и треугольника», Журнал ACM, 65 (5): A27: 1 – A27: 38, Дои:10.1145/3186893, Г-Н 3856539. Предварительная версия этих результатов, включая определение «субкубической редукции», частного случая мелкозернистой редукции, была представлена на конференции 2010 г. Симпозиум по основам информатики.
^ Кармозино, Марко Л .; Гао, Цзявэй; Импальяццо, Рассел; Михайлин, Иван; Патури, Рамамохан; Шнайдер, Стефан (2016), "Недетерминированные расширения сильной гипотезы экспоненциального времени и следствия для несводимости", ITCS'16 - Материалы конференции ACM по инновациям в теоретической информатике 2016 г., ACM, Нью-Йорк, стр. 261–270, Г-Н 3629829

[w15-1] а ^б ^c ^d ^е ^ж Уильямс, Вирджиния В. (2015), «Трудность простых задач: твердость основывается на популярных гипотезах, таких как сильная гипотеза экспоненциального времени», 10-й Международный симпозиум по параметризованным и точным вычислениям, LIPIcs. Leibniz Int. Proc. Сообщить., 43, Schloss Dagstuhl. Лейбниц-Цент. Информ., Вадерн, стр. 17–29, Г-Н 3452406

[ww10-2] Уильямс, Вирджиния Василевска; Уильямс, Р. Райан (2018), «Субкубические эквивалентности между задачами пути, матрицы и треугольника», Журнал ACM, 65 (5): A27: 1 – A27: 38, Дои:10.1145/3186893, Г-Н 3856539. Предварительная версия этих результатов, включая определение «субкубической редукции», частного случая мелкозернистой редукции, была представлена на конференции 2010 г. Симпозиум по основам информатики.

[cgimps-3] Кармозино, Марко Л .; Гао, Цзявэй; Импальяццо, Рассел; Михайлин, Иван; Патури, Рамамохан; Шнайдер, Стефан (2016), "Недетерминированные расширения сильной гипотезы экспоненциального времени и следствия для несводимости", ITCS'16 - Материалы конференции ACM по инновациям в теоретической информатике 2016 г., ACM, Нью-Йорк, стр. 261–270, Г-Н 3629829

[1]

[2]

[3]