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

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

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

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

Они задают проблемы

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

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

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

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

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

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

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

Общий пример

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

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

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

f_{u}^{\otimes |U|}f_{v}^{\otimes |V|}

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

=\left(f_{u}T^{\otimes (\deg u)}\right)^{\otimes |U|}\left(f_{v}(T^{-1})^{\otimes (\deg v)}\right)^{\otimes |V|}.

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

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

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

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

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

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

=(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|}

=(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|}

=\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|}

=(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|}

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

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

История

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

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

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

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

Ссылки

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

[valiant-1] Jump up to: ^а ^б ^с Валиант, Лесли (17–19 октября 2004 г.). Голографические алгоритмы (Расширенное резюме) . ФОКС 2004 . Рим, Италия: Компьютерное общество IEEE. стр. 306–315. дои : 10.1109/FOCS.2004.34 . ISBN 0-7695-2228-9 .

[americanscientist-2] Jump up to: ^а ^б Хейс, Брайан (январь – февраль 2008 г.). «Случайные алгоритмы» . Американский учёный .

[art-3] Jump up to: ^а ^б ^с Цай, Джин-И; Лу, Пиньян (2011). «Голографические алгоритмы: От искусства к науке» . Дж. Компьютер. Сист. Наука . 77 (1): 41–61. дои : 10.1016/j.jcss.2010.06.005 .

[survey-4] Цай, Джин-И (июнь 2008 г.). «Голографические алгоритмы: гостевая колонка». Новости СИГАКТ . 39 (2). Нью-Йорк, штат Нью-Йорк, США: ACM: 51–81. дои : 10.1145/1388240.1388254 . ISSN 0163-5700 . S2CID 2298274 .

[fibonacci-5] Jump up to: ^а ^б Цай, Джин-И; Лу, Пиньян; Ся, Минджи (2008). Голографические алгоритмы ворот Фибоначчи и голографические редукции твердости . ФОКС . Компьютерное общество IEEE. стр. 644–653. дои : 10.1109/FOCS.2008.34 . ISBN 978-0-7695-3436-7 .

[6] Валиант, Лесли (2002). «Квантовые схемы, которые можно классически моделировать за полиномиальное время». SIAM Journal по вычислительной технике . 31 (4): 1229–1254. дои : 10.1137/S0097539700377025 .

[7] Лесли Дж. Валиант (2006). Случайные алгоритмы [ Случайные алгоритмы ]. Основы информатики, Ежегодный симпозиум IEEE. Компьютерное общество IEEE. стр. 509–517. дои : 10.1109/FOCS.2006.7 . ISBN 0-7695-2720-5 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]