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

Алгоритм с использованием голографической редукции

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

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

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

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

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

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

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

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

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

Голографическое уменьшение

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

Общий пример

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

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

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

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

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

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

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

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

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

${\displaystyle =(0,1,1,1)^{\otimes |U|}\left({\begin{bmatrix}1\\0\end{bmatrix}}^{\otimes 3}+{\begin{bmatrix}0\\1\end{bmatrix}}^{\otimes 3}\right)^{\otimes |V|}}$

${\displaystyle =(0,1,1,1)^{\otimes |U|}{\begin{bmatrix}0&1\\1&0\end{bmatrix}}^{\otimes |E|}{\begin{bmatrix}0&1\\1&0\end{bmatrix}}^{\otimes |E|}\left({\begin{bmatrix}1\\0\end{bmatrix}}^{\otimes 3}+{\begin{bmatrix}0\\1\end{bmatrix}}^{\otimes 3}\right)^{\otimes |V|}}$

${\displaystyle =\left((0,1,1,1){\begin{bmatrix}0&1\\1&0\end{bmatrix}}^{\otimes 2}\right)^{\otimes |U|}\left(\left({\begin{bmatrix}0&1\\1&0\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}\right)^{\otimes 3}+\left({\begin{bmatrix}0&1\\1&0\end{bmatrix}}{\begin{bmatrix}0\\1\end{bmatrix}}\right)^{\otimes 3}\right)^{\otimes |V|}}$

${\displaystyle =(1,1,1,0)^{\otimes |U|}\left({\begin{bmatrix}0\\1\end{bmatrix}}^{\otimes 3}+{\begin{bmatrix}1\\0\end{bmatrix}}^{\otimes 3}\right)^{\otimes |V|}}$

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

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

История

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

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

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

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

Ссылки

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