Голографический алгоритм - Holographic algorithm

Для голографической памяти (которая не имеет отношения) см. Голографическое хранилище данных.

В Информатика, а голографический алгоритм представляет собой алгоритм, использующий голографическую редукцию. Голографическая редукция - это постоянное время снижение который отображает фрагменты решения «многие ко многим», так что сумма фрагментов решения остается неизменной. Эти концепции были введены Лесли Валиант, кто назвал их голографический потому что «их эффект можно рассматривать как эффект создания интерференционной картины среди фрагментов раствора».^[1] Алгоритмы не имеют отношения к лазеру голография, кроме переносного. Их сила происходит от взаимного подавления многих вкладов в сумму, аналогично интерференционным картинам в голограмме.^[2]

Голографические алгоритмы были использованы для поиска полиномиальное время решения проблем без таких ранее известных решений для частных случаев выполнимость, крышка вершины, и другие проблемы с графиком.^[3] Они получили заметное освещение из-за предположений, что они имеют отношение к P против проблемы NP^[2] и их влияние на теория сложности вычислений. Хотя некоторые из общих проблем # P-hard Решенные частные случаи сами по себе не являются # P-сложными и, следовательно, не доказывают, что FP = #P.

Голографические алгоритмы имеют некоторое сходство с квантовые вычисления, но полностью классические.^[4]

Проблемы Холанта

Голографические алгоритмы существуют в контексте проблем Холанта, которые обобщают подсчет проблемы удовлетворения ограничений (#CSP). Экземпляр #CSP - это гиперграф грамм=(V,E) называется граф ограничений. Каждое гиперребро представляет собой переменную, а каждая вершина ${displaystyle v}$ назначается ограничение ${displaystyle f_{v}.}$ Вершина соединяется с гиперребром, если ограничение на вершину включает переменную на гиперребре. Проблема подсчета состоит в том, чтобы вычислить

${displaystyle sum _{sigma :E o {0,1}}prod _{vin V}f_{v}(sigma |_{E(v)}),~~~~~~~~~~(1)}$

который является суммой по всем присвоениям переменных, произведением каждого ограничения, где входные данные для ограничения ${displaystyle f_{v}}$ - переменные на инцидентных гиперребрах ${displaystyle v}$.

Проблема Холанта похожа на #CSP, за исключением того, что входные данные должны быть графом, а не гиперграфом. Такое ограничение класса входных графов действительно является обобщением. Учитывая экземпляр #CSP, замените каждое гиперребро е размера s с вершиной v степени s с ребрами, инцидентными вершинам, содержащимся в е. Ограничение на v - функция равенства арности s. Это идентифицирует все переменные на ребрах, инцидентных v, что аналогично влиянию единственной переменной на гиперреберье е.

В контексте проблем Холанта выражение в (1) называется Холантом в честь соответствующей экспоненциальной суммы, введенной Валиантом.^[5]

Голографическая редукция

Стандартный метод в теории сложности - это много-одно сокращение, где экземпляр одной задачи сводится к экземпляру другой (надеюсь, более простой) проблемы. Однако голографические сокращения между двумя вычислительными задачами сохраняют сумму решений, не обязательно сохраняя соответствия между решениями.^[1] Например, общее количество решений в обоих наборах может быть сохранено, даже если отдельные проблемы не имеют подходящих решений. Сумму также можно взвесить, а не просто подсчитывать количество решений, используя линейные базисные векторы.^[3]

Общий пример

Голографические редукции удобно рассматривать на двудольных графах. Общий граф всегда можно преобразовать в двудольный граф с сохранением значения Холанта. Это делается путем замены каждого ребра в графе путем длиной 2, который также известен как 2-участок графа. Чтобы сохранить то же значение Холанта, каждой новой вершине назначается ограничение двоичного равенства.

Рассмотрим двудольный граф грамм=(U,V,E), где ограничение на каждую вершину ${displaystyle uin U}$ является ${displaystyle f_{u}}$ и ограничение, назначенное каждой вершине ${displaystyle vin V}$ является ${displaystyle f_{v}}$. Обозначим эту задачу подсчета как ${displaystyle { ext{Holant}}(G,f_{u},f_{v}).}$ Если вершины в U рассматриваются как одна большая вершина степени |E|, то ограничением этой вершины является тензорное произведение из ${displaystyle f_{u}}$ с собой |U| раз, что обозначается ${displaystyle f_{u}^{otimes |U|}.}$ Аналогично, если вершины в V рассматриваются как одна большая вершина степени |E|, то ограничение этой вершины равно ${displaystyle f_{v}^{otimes |V|}.}$ Пусть ограничение ${displaystyle f_{u}}$ быть представлен его взвешенным таблица истинности как вектор-строку и ограничение ${displaystyle f_{v}}$ быть представлен его взвешенной таблицей истинности как вектор-столбец. Тогда Холант этого графа ограничений просто ${displaystyle f_{u}^{otimes |U|}f_{v}^{otimes |V|}.}$

Теперь для любого комплекса 2 на 2 обратимая матрица Т (столбцы которых являются линейными базисными векторами, упомянутыми выше), существует голографическая редукция между ${displaystyle { ext{Holant}}(G,f_{u},f_{v})}$ и ${displaystyle { ext{Holant}}(G,f_{u}T^{otimes (deg u)},(T^{-1})^{otimes (deg v)}f_{v}).}$ Чтобы увидеть это, вставьте единичную матрицу ${displaystyle T^{otimes |E|}(T^{-1})^{otimes |E|}}$ между ${displaystyle f_{u}^{otimes |U|}f_{v}^{otimes |V|}}$ получить

${displaystyle f_{u}^{otimes |U|}f_{v}^{otimes |V|}}$

${displaystyle =f_{u}^{otimes |U|}T^{otimes |E|}(T^{-1})^{otimes |E|}f_{v}^{otimes |V|}}$

${displaystyle =left(f_{u}T^{otimes (deg u)}ight)^{otimes |U|}left(f_{v}(T^{-1})^{otimes (deg v)}ight)^{otimes |V|}.}$

Таким образом, ${displaystyle { ext{Holant}}(G,f_{u},f_{v})}$ и ${displaystyle { ext{Holant}}(G,f_{u}T^{otimes (deg u)},(T^{-1})^{otimes (deg v)}f_{v})}$ имеют точно такое же значение Холанта для каждого графа ограничений. По сути, они определяют одну и ту же проблему счета.

Конкретные примеры

Покрытия вершин и независимые множества

Позволять грамм быть графом. Существует соответствие 1: 1 между вершинные крышки из грамм и независимые множества из грамм. Для любого набора S вершин грамм, S является вершинным покрытием в грамм если и только если дополнять из S является независимым множеством в грамм. Таким образом, количество вершинных покрытий в грамм точно так же, как количество независимых множеств в грамм.

Эквивалентность этих двух задач подсчета также может быть доказана с помощью голографической редукции. Пусть для простоты грамм быть 3-регулярный график. 2-х отрезок грамм дает двудольный граф ЧАС=(U,V,E), куда U соответствует ребрам в грамм и V соответствует вершинам в грамм. Задача Холанта, которая, естественно, соответствует подсчету числа вершинных покрытий в грамм является ${displaystyle { ext{Holant}}(H,{ ext{OR}}_{2},{ ext{EQUAL}}_{3}).}$ Таблица истинности OR₂ как вектор-строка (0,1,1,1). Таблица истинности EQUAL₃ как вектор-столбец ${displaystyle (1,0,0,0,0,0,0,1)^{T}={egin{bmatrix}1�end{bmatrix}}^{otimes 3}+{egin{bmatrix}01end{bmatrix}}^{otimes 3}}$. Тогда при голографическом преобразовании ${displaystyle {egin{bmatrix}0&11&0end{bmatrix}},}$

${displaystyle { ext{OR}}_{2}^{otimes |U|}{ ext{EQUAL}}_{3}^{otimes |V|}}$

${displaystyle =(0,1,1,1)^{otimes |U|}left({egin{bmatrix}1�end{bmatrix}}^{otimes 3}+{egin{bmatrix}01end{bmatrix}}^{otimes 3}ight)^{otimes |V|}}$

${displaystyle =(0,1,1,1)^{otimes |U|}{egin{bmatrix}0&11&0end{bmatrix}}^{otimes |E|}{egin{bmatrix}0&11&0end{bmatrix}}^{otimes |E|}left({egin{bmatrix}1�end{bmatrix}}^{otimes 3}+{egin{bmatrix}01end{bmatrix}}^{otimes 3}ight)^{otimes |V|}}$

${displaystyle =left((0,1,1,1){egin{bmatrix}0&11&0end{bmatrix}}^{otimes 2}ight)^{otimes |U|}left(left({egin{bmatrix}0&11&0end{bmatrix}}{egin{bmatrix}1�end{bmatrix}}ight)^{otimes 3}+left({egin{bmatrix}0&11&0end{bmatrix}}{egin{bmatrix}01end{bmatrix}}ight)^{otimes 3}ight)^{otimes |V|}}$

${displaystyle =(1,1,1,0)^{otimes |U|}left({egin{bmatrix}01end{bmatrix}}^{otimes 3}+{egin{bmatrix}1�end{bmatrix}}^{otimes 3}ight)^{otimes |V|}}$

${displaystyle ={ ext{NAND}}_{2}^{otimes |U|}{ ext{EQUAL}}_{3}^{otimes |V|},}$

который ${displaystyle { ext{Holant}}(H,{ ext{NAND}}_{2},{ ext{EQUAL}}_{3}),}$ проблема Холанта, которая, естественно, соответствует подсчету числа независимых множеств в грамм.

История

Как и любой тип редукции, голографическая редукция сама по себе не дает алгоритма с полиномиальным временем. Чтобы получить алгоритм с полиномиальным временем, задача, к которой сводится, также должна иметь алгоритм с полиномиальным временем. Первоначальное приложение голографических алгоритмов Valiant использовало голографическую редукцию к проблеме, где каждое ограничение реализуемо ворота,^[1] которое он только что доказал, можно смирить путем дальнейшего сведения к подсчету числа идеальное соответствие в планарный граф.^[6] Последняя проблема решается Алгоритм FKT, который датируется 1960-ми годами.

Вскоре после этого Valiant обнаружил голографические алгоритмы с редукциями до совпадений для #₇Pl -Rtw-Пн -3CNF и #₇Пл-3/2Bip -ВК.^[7] Эти проблемы могут показаться несколько надуманными, особенно в отношении модуль. Обе задачи уже были известны как # P-жесткие при игнорировании модуля, и Valiant предоставил доказательства # P-жесткости по модулю 2, которые также использовали голографические сокращения. Valiant обнаружил эти две проблемы с помощью компьютерного поиска, который искал проблемы с голографическими редукциями к матчевым воротам. Он назвал свои алгоритмы случайные алгоритмы, в котором говорится, что «применяя термин случайный к алгоритму, мы намереваемся указать, что алгоритм возникает из удовлетворения явно обременительного набора ограничений». Рассматриваемый «обременительный» набор ограничений представляет собой полиномиальные уравнения, которые, если они выполняются, подразумевают существование голографической редукции для соответствия реализуемым ограничениям.

После нескольких лет разработки (так называемой) теории сигнатур совпадений, Джин-И Цай и Пиньян Лу смогли объяснить существование двух случайных алгоритмов Valiant.^[3] Эти две проблемы - лишь частные случаи двух гораздо больших семейств проблем: #_2^k-1Pl-Rtw-Mon-kCNF и #_2^k-1Pl-k / 2Bip-VC для любого положительного целого числа k. Модуль 7 - это всего лишь третий Число Мерсенна и Цай и Лу показали, что эти типы задач с параметром k может быть решена за полиномиальное время, когда модуль равен k-го числа Мерсенна с помощью голографических сокращений для матчевых ворот и Китайская теорема об остатках.

Примерно в то же время Цзинь-И Цай, Пиньян Лу и Минцзи Ся разработали первый голографический алгоритм, который не сводился к проблеме, которую можно решить с помощью ворот.^[5] Вместо этого они свелись к проблеме, которую можно решить с помощью ворот Фибоначчи, которые симметричный ограничения, таблицы истинности которых удовлетворяют отношение повторения аналогичен тому, который определяет Числа Фибоначчи. Они также использовали голографические редукции, чтобы доказать, что некоторые задачи счета являются # P-сложными. С тех пор голографические редукции широко использовались как ингредиенты как в алгоритмах полиномиального времени, так и в качестве доказательства # P-твердости.

Рекомендации

1. Доблестный, Лесли (17–19 октября 2004 г.). Голографические алгоритмы (расширенное резюме). FOCS 2004. Рим, Италия: Компьютерное общество IEEE. С. 306–315. Дои:10.1109 / FOCS.2004.34. ISBN  0-7695-2228-9.
2. Хейс, Брайан (Январь – февраль 2008 г.). «Случайные алгоритмы». Американский ученый.
3. Цай, Цзинь-И; Лу, Пинян (2011). «Голографические алгоритмы: от искусства к науке». J. Comput. Syst. Наука. 77 (1): 41–61. Дои:10.1016 / j.jcss.2010.06.005.
4. Цай, Цзинь-И (июнь 2008 г.). «Голографические алгоритмы: гостевая колонка». Новости SIGACT. Нью-Йорк, Нью-Йорк, США: ACM. 39 (2): 51–81. Дои:10.1145/1388240.1388254. ISSN  0163-5700.
5. Цай, Цзинь-И; Лу, Пиньян; Ся, Минцзи (2008). Голографические алгоритмы ворот Фибоначчи и голографические редукции твердости. FOCS. Компьютерное общество IEEE. С. 644–653. Дои:10.1109 / FOCS.2008.34. ISBN  978-0-7695-3436-7.
6. Доблестный, Лесли (2002). «Квантовые схемы, которые можно моделировать классическим способом за полиномиальное время». SIAM Журнал по вычислениям. 31 (4): 1229–1254. Дои:10.1137 / S0097539700377025.
7. Лесли Г. Валиант (2006). Случайные Альгортимы [Случайные алгоритмы]. Основы компьютерных наук, Ежегодный симпозиум IEEE по. Компьютерное общество IEEE. С. 509–517. Дои:10.1109 / FOCS.2006.7. ISBN  0-7695-2720-5.