♯П-полнота 01-перманент

# P -полнота 01-перманента , иногда известная как теорема Валианта , Это математическое доказательство перманента , матриц вычислений считающееся основополагающим результатом в теории сложности . В научной статье вычислительная 1979 года Лесли Валиант доказал, что проблема вычисления перманента матрицы является #P-трудной , даже если в матрице есть ограничения на наличие всех элементов, равных 0 или 1. В этом ограниченном случае вычисление перманента является даже #P-полным , поскольку оно соответствует задаче #P подсчёта количества матриц перестановок, которые можно получить, заменив единицы на нули.

В статье Валианта 1979 года также был представлен #P как класс сложности .

В определении полноты Валианта и его доказательстве полноты 01-перманента использовались за полиномиальное время сокращения Тьюринга . При таком виде сокращения единственный сложный экземпляр какой-либо другой проблемы в #P сводится к вычислению перманента последовательности нескольких графов, каждый из которых потенциально может зависеть от результатов предыдущих перманентных вычислений. Более позднее упрощение, предложенное Бен-Дором и Халеви (1993), показало, что можно использовать более слабое понятие редукции, редукцию подсчета за полиномиальное время , которая переводит другую проблему в единственный экземпляр постоянной проблемы.

Значение

Одна из причин интереса к вычислительной сложности перманента заключается в том, что он представляет собой пример задачи, в которой построение единственного решения может быть выполнено эффективно, но подсчет всех решений затруднен. Как пишет Пападимитриу в своей книге «Вычислительная сложность» :

Наиболее впечатляющими и интересными #P-полными задачами являются те, для которых соответствующая задача поиска может быть решена за полиномиальное время. Классическим примером здесь является ПОСТОЯННАЯ проблема для матриц 0–1, которая эквивалентна проблеме подсчета идеальных паросочетаний в двудольном графе [...].

В частности, вычисление перманента (как показали результаты Валианта, это сложно) тесно связано с поиском идеального паросочетания в двудольном графе , который разрешим за полиномиальное время с помощью алгоритма Хопкрофта-Карпа . Для двудольного графа с 2n вершинами, разделенными на две части по n вершин в каждой, количество идеальных паросочетаний равно перманенту его матрицы двусмежности , а квадрат числа совершенных паросочетаний равен перманенту его матрицы смежности . Поскольку любая матрица 0–1 является матрицей двусмежности некоторого двудольного графа, из теоремы Валианта следует что проблема подсчета количества идеальных паросочетаний в двудольном графе является #P-полной , и в сочетании с теоремой Тоды это означает, что она сложна для всей полиномиальной иерархии .

Вычислительная сложность перманента также имеет некоторое значение в других аспектах теории сложности: неизвестно, равно ли NC с полилогарифмическим временем P (неформально, может ли каждая полиномиально решаемая задача быть решена с помощью параллельного алгоритма ), и Кетан Малмули предположил, что подход к решению этого вопроса, основанный на записи перманента как определителя матрицы.

Хартманн доказал обобщение теоремы Валианта о сложности вычисления имманантов матриц , обобщающих как определитель, так и перманент.

Доказательство Бен-Дора и Халеви

доказательство того, что вычисление перманента 01-матрицы #P-полно Ниже описано . В основном оно следует доказательству Бен-Дора и Халеви (1993) .

Обзор

Любая квадратная матрица $A=(a_{ij})$ можно рассматривать как матрицу смежности ориентированного графа, где $a_{ij}$ представляющий вес ребра из вершины $i$ в вершину $j$. Затем перманент $A$ равен сумме весов всех циклопокрытий графа; это теоретико-графовая интерпретация постоянного .

#SAT , функциональная задача , связанная с проблемой булевой выполнимости , представляет собой задачу подсчета количества удовлетворяющих назначений данной булевой формулы. Это #P-полная проблема (по определению), поскольку любая NP-машина может быть закодирована в булевую формулу с помощью процесса, аналогичного процессу в теореме Кука , так что количество удовлетворяющих присвоений булевой формулы равно числу приемных путей машины NP. Любую формулу в SAT можно переписать как формулу в форме 3- CNF , сохраняя количество удовлетворяющих присваиваний, поэтому #SAT и #3SAT эквивалентны, а #3SAT #P-полна также .

Поэтому, чтобы доказать, что 01-Permanent является #P-hard , достаточно показать, что количество удовлетворяющих присвоений для формулы 3-CNF может быть кратко выражено как функция перманента матрицы, которая содержит только значения 0 и 1. Обычно это выполняется в два этапа:

1. Учитывая формулу 3-CNF $\phi$, построим направленный целочисленно-взвешенный граф $G_{\phi }$, такой, что сумма весов циклических покрытий $G_{\phi }$ (или, что то же самое, перманент ее матрицы смежности) равен количеству удовлетворяющих присвоений $\phi$. Это устанавливает, что постоянный является #P-сложным.
2. Посредством серии сокращений сведите постоянный к 01-постоянному, задаче вычисления перманента матрицы для всех записей 0 или 1. Это устанавливает, что 01-постоянный также является #P-сложным.

Построение целочисленного графа

Учитывая 3CNF-формулу $\phi$ с $m$ положения и $n$ переменных, можно построить взвешенный ориентированный граф $G_{\phi }$ такой, что

1. каждое удовлетворяющее задание для $\phi$ будет иметь соответствующий набор обложек циклов в $G_{\phi }$ где сумма весов покрытий циклов в этом множестве будет равна $12^{m}$ ; и
2. все остальные циклы охватывают $G_{\phi }$ будут иметь веса, суммирующиеся до 0.

Таким образом, если $(\#\phi )$ это количество удовлетворяющих заданий для $\phi$, перманент этого графика будет $12^{m}\cdot (\#\phi )$. (Оригинальное доказательство Валианта строит граф с элементами в $\{-1,0,1,2,3\}$ чей перманент $4^{t(\phi )}\cdot (\#\phi )$ где $t(\phi )$ «вдвое больше вхождений литералов в $\phi$"- $m$.)

В конструкции графа используется компонент, который рассматривается как «черный ящик». Для простоты объяснения свойства этого компонента приводятся без фактического определения структуры компонента.

Чтобы указать $G_{\phi }$, сначала создается переменный узел в $G_{\phi }$ для каждого из $n$ переменные в $\phi$. Кроме того, для каждого из $m$ положения в $\phi$, создается компонент предложения $C_{j}$ в $G_{\phi }$ это действует как своего рода «черный ящик». Все, что необходимо отметить по поводу $C_{j}$ заключается в том, что он имеет три входных и три выходных фронта. Входные ребра поступают либо из узлов переменных, либо из компонентов предыдущего предложения (например, $C_{i}$ для некоторых $i<j$), а выходные ребра переходят либо к узлам переменных, либо к более поздним компонентам предложения (например, $C_{i}$ для некоторых $o>j$). Первые входные и выходные ребра соответствуют первой переменной предложения. $j$, и так далее. На данный момент все узлы, которые появятся на графике $G_{\phi }$ были указаны.

Далее следует рассмотреть края. Для каждой переменной $x_{i}$ из $\phi$, можно создать истинный цикл (Т-цикл) и ложный цикл (F-цикл) в $G_{\phi }$. Чтобы создать Т-цикл, мы начинаем с узла переменной для $x_{i}$ и нарисуйте край компонента предложения $C_{j}$ что соответствует первому предложению, в котором $x_{i}$ появляется. Если $x_{i}$ — первая переменная в предложении $\phi$ соответствующий $C_{j}$, это ребро будет первым входным ребром $C_{j}$, и так далее. Затем нарисуйте ребро к следующему компоненту предложения, соответствующему следующему предложению $\phi$ в котором $x_{i}$ появится, подключив его к соответствующему выходному краю $C_{j}$ к соответствующему входному ребру следующего компонента предложения и так далее. После последнего предложения, в котором $x_{i}$ появляется, мы подключаем соответствующий выходной край соответствующего компонента предложения обратно к $x_{i}$переменная node. Конечно, это завершает цикл. Чтобы создать F-цикл, нужно было бы выполнить ту же процедуру, но подключить $x_{i}$узел переменной для тех компонентов предложения, в которых ~ $x_{i}$ появляется и, наконец, возвращается к $x_{i}$переменная node. Все эти ребра вне компонентов предложения называются внешними ребрами , все из которых имеют вес 1. Внутри компонентов предложения ребра называются внутренними ребрами . Каждое внешнее ребро является частью Т-цикла или F-цикла (но не того и другого — это приведет к несогласованности).

Обратите внимание, что график $G_{\phi }$ имеет размер, линейный по $|\phi |$, поэтому построение можно выполнить за политайм (при условии, что компоненты предложения не вызывают проблем).

Примечательные свойства графа

Полезное свойство $G_{\phi }$ заключается в том, что его покрытия циклов соответствуют присвоениям переменных для $\phi$. Для велосипедного чехла $Z$ из $G_{\phi }$, можно сказать, что $Z$ вызывает присвоение значений переменным в $\phi$ на всякий случай $Z$ содержит все внешние ребра в $x_{i}$T-цикл и ни одно из внешних ребер в $x_{i}$F-цикл для всех переменных $x_{i}$ что присваивание становится истинным, и наоборот для всех переменных $x_{i}$ что присваивание делает ложным. Хотя любое данное покрытие цикла $Z$ не нужно вызывать задание для $\phi$, любой, который это делает, индуцирует ровно одно присваивание, и то же самое индуцированное присваивание зависит только от внешних ребер $Z$. Термин $Z$ на этом этапе считается покрытием неполного цикла, поскольку речь идет только о его внешних краях, $M$. В разделе ниже рассматривается $M$-дополнения, чтобы показать, что имеется набор покрытий циклов, соответствующий каждому $M$ обладающие необходимыми свойствами.

Какие обложки $Z$ которые не вызывают присваивания, — это те, которые содержат циклы, которые «перескакивают» внутрь компонентов предложения. То есть, если для каждого $C_{j}$, хотя бы один из $C_{j}$входные края находятся в $Z$, и каждое выходное ребро компонентов предложения находится в $Z$ когда соответствующий входной фронт находится в $Z$, затем $Z$ является правильным по отношению к каждому компоненту предложения, и $Z$ подготовит удовлетворительное задание для $\phi$. Это потому, что правильные покрытия $Z$ содержат либо полный T-цикл, либо полный F-цикл каждой переменной $x_{i}$ в $\phi$ а также каждое из ребер, входящих и выходящих из каждого компонента предложения. Таким образом, эти покрытия присваивают каждому из них либо истинное, либо ложное (но никогда то и другое). $x_{i}$ и обеспечить выполнение каждого пункта. Далее, множества цикловых накрытий, соответствующие всем таким $Z$ иметь вес $12^{m}$и любые другие $Z$ имеет вес $0$. Причины этого зависят от конструкции компонентов предложения и изложены ниже.

Компонент предложения

Понять соответствующие свойства компонентов предложения. $C_{j}$, необходимо понятие М-пополнения. Велосипедный чехол $Z$ индуцирует удовлетворяющее присваивание только в том случае, если его внешние ребра удовлетворяют определенным свойствам. Для любого цикла покрытия $G_{\phi }$, рассмотрим только его внешние ребра, подмножество $M$. Позволять $M$ быть множеством внешних ребер. Набор внутренних ребер $L$ это $M$-завершение на всякий случай $M\cup L$ это обложка цикла $G_{\phi }$. Далее обозначим множество всех $M$-завершения $L^{M}$ и множество всех результирующих покрытий циклов $G_{\phi }$ к $Z^{M}$.

Напомним, что строительство $G_{\phi }$ было таково, что каждое внешнее ребро имело вес 1, поэтому вес $Z^{M}$, цикл охватывает результат любого $M$, зависит только от задействованных внутренних ребер. Добавим сюда предпосылку, что конструкция компонентов предложения такова, что сумма по возможным $M$-дополнения веса внутренних ребер в каждом компоненте предложения, где $M$ является правильным относительно компонента предложения, равен 12. В противном случае вес внутренних ребер равен 0. Поскольку существуют $m$ компоненты предложения и выбор наборов внутренних ребер, $L$, внутри каждого компонента предложения не зависит от выбора наборов внутренних ребер в других компонентах предложения, поэтому можно все перемножить, чтобы получить вес $Z^{M}$. Итак, вес каждого $Z^{M}$, где $M$ индуцирует удовлетворяющее задание, $12^{m}$. Далее, где $M$ не приводит к удовлетворительному заданию, $M$ некорректно по отношению к некоторым $C_{j}$, поэтому произведение весов внутренних ребер в $Z^{M}$ будет $0$.

Компонент предложения представляет собой взвешенный ориентированный граф с 7 узлами со взвешенными ребрами и узлами, расположенными так, чтобы обеспечить свойства, указанные выше, и приведен в Приложении A Бен-Дора и Халеви (1993). Обратите внимание, что внутренние ребра здесь имеют веса, взятые из набора $\{-1,0,1,2,3\}$; не все ребра имеют веса 0–1.

Наконец, поскольку сумма весов всех наборов циклических покрытий, индуцирующих какое-либо конкретное удовлетворяющее присваивание, равна $12^{m}$, а сумма весов всех остальных наборов покрытий циклов равна 0, имеем $\operatorname {Perm} (G_{\phi })=12^{m}\cdot (\#\phi )$. В следующем разделе сокращаются вычисления $\operatorname {Perm} (G_{\phi })$ перманенту матрицы 01.

01-Матрица

В приведенном выше разделе показано, что постоянный является #P-сложным. Путем серии сокращений любой перманент можно свести к перманенту матрицы с элементами только 0 или 1. Это докажет, что 01-Permanent также является #P-сложным.

Приведение к неотрицательной матрице

Используя модульную арифметику , преобразуйте целочисленную матрицу $A$ в эквивалентную неотрицательную матрицу $A'$ так что перманент $A$ можно легко вычислить из перманента $A'$, следующее:

Позволять $A$ быть $n\times n$ целочисленная матрица, где ни одна запись не имеет величины больше, чем $\mu$.

• Вычислить $Q=2\cdot n!\cdot \mu ^{n}+1$. Выбор $Q$ связано с тем, что $|\operatorname {Perm} (A)|\leq n!\cdot \mu ^{n}$
• Вычислить $A'=A\,{\bmod {\,}}Q$
• Вычислить $P=\operatorname {Perm} (A'){\bmod {Q}}$
• Если $P<Q/2$ тогда Пермь( А ) = П . В противном случае $\operatorname {Perm} (A)=P-Q$

Преобразование $A$ в $A'$ полиномиален по $n$ и $\log(\mu )$, поскольку количество битов, необходимое для представления $Q$ полиномиален по $n$ и $\log(\mu )$

Пример преобразования и почему оно работает приведен ниже.

$A={\begin{bmatrix}2&-2\\-2&1\end{bmatrix}}$

$\operatorname {Perm} (A)=2\cdot 1+(-2)\cdot (-2)=6.$

Здесь, $n=2$, $\mu =2$, и $\mu ^{n}=4$, так $Q=17$. Таким образом

$A'=A{\bmod {1}}7={\begin{bmatrix}2&15\\15&1\end{bmatrix}}.$

Обратите внимание, что элементы неотрицательны благодаря модульной арифметике. Вычислить постоянную величину несложно.

$\operatorname {Perm} (A')=2\cdot 1+15\cdot 15=227$

так $P=227{\bmod {1}}7=6$. Затем $P<Q/2$, так $\operatorname {Perm} (A)=P=6.$

Приведение к степени 2

Figure 1: Construction of 2Power from NonNeg

Обратите внимание, что любое число можно разложить в сумму степеней 2 . Например,

$13=2^{3}+2^{2}+2^{0}$

Этот факт используется для преобразования неотрицательной матрицы в эквивалентную матрицу, все элементы которой являются степенями 2. Сокращение может быть выражено с помощью графиков, эквивалентных матрицам.

Позволять $G$ быть $n$-взвешенный по узлам ориентированный граф с неотрицательными весами, где наибольший вес равен $W$. Каждый край $e$ с весом $w$ преобразуется в эквивалентное ребро с весами в степенях 2 следующим образом:

$w=2^{x_{1}}+2^{x_{2}}+\cdots +2^{x_{r}}$, $0\leq x_{1}\leq x_{2}\leq \cdots \leq x_{r}\leq \log(w)$

Графически это можно увидеть на рисунке 1. Подграф, заменяющий существующее ребро, содержит $r$ узлы и $3r$ края.

Чтобы доказать, что это дает эквивалентный граф $G'$ имеющий тот же перманент, что и оригинал, необходимо показать соответствие между обложками цикла $G$ и $G'$.

Рассмотрим некоторое циклическое покрытие $R$ в $G$.

• Если край $e$ не в $R$, то чтобы охватить все узлы нового подграфа, необходимо использовать циклы. Поскольку все циклы имеют вес 1, вес циклических накрытий в $R$ и $R'$ соответствовать.
• Если $e$ находится в $R$, то во всех соответствующих цикло-накрытиях из $G'$, должен быть путь из $u$ к $v$, где $u$ и $v$ являются узлами ребра $e$. Из конструкции видно, что есть $r$ разные пути и сумма всех этих путей равна весу ребра в исходном графе $G$. Таким образом, вес соответствующих циклопокрытий в $G$ и $G'$ соответствовать.

Обратите внимание, что размер $G'$ полиномиален по $n$ и $\log W$.

Снижение до 0–1

Figure 2: Construction of a 01-matrix from 2Power

Цель здесь состоит в том, чтобы свести матрицу, элементы которой являются степенями 2, в эквивалентную матрицу, содержащую только нули и единицы (т.е. ориентированный граф, где каждое ребро имеет вес 1).

Позволять $G$ быть $n$-узловой ориентированный граф, в котором все веса на ребрах являются степенями двойки. Построить график, $G'$, где вес каждого ребра равен 1 и $\operatorname {Perm} (G)=\operatorname {Perm} (G')$. Размер этого нового графика, $(G')$, является полиномиальным по $n$ и $p$ где максимальный вес любого ребра графа $G$ является $2^{p}$.

Это сокращение выполняется локально на каждом ребре $G$ который имеет вес больше 1. Пусть $e=(u,v)$ быть преимуществом в $G$ с весом $w=2^{r}>1$. Его заменяет подграф $J_{e}$ который состоит из $2r$ узлы и $6r$ ребра, как показано на рисунке 2. Каждое ребро в $J_{e}$ имеет вес 1. Таким образом, полученный граф $G'$ содержит только ребра с весом 1.

Рассмотрим некоторое циклическое покрытие $R$ в $G$.

• Если исходный край $e$ из графика $G$ не в $R$, нельзя создать путь через новый подграф $J_{e}$. Единственный способ сформировать циклическое покрытие над $J_{e}$ в таком случае каждый узел подграфа должен взять свой цикл. Поскольку вес каждого ребра равен единице, вес полученного покрытия цикла равен весу исходного покрытия цикла.
• Однако, если край в $G$ является частью покрытия цикла, то в любом покрытии цикла $G'$ должен быть путь из $u$ к $v$ в подграфе. На каждом шаге вниз по подграфу можно сделать два варианта формирования такого пути. Человек должен сделать этот выбор $r$ раз, что приводит к $2^{r}$ возможные пути из $u$ к $v$. Таким образом, существуют $2^{r}$ возможных покрытий цикла, и поскольку каждый путь имеет вес 1, сумма весов всех этих покрытий цикла равна весу исходного покрытия цикла.

Доказательство Ааронсона

В 2011 году специалист по квантовым компьютерам Скотт Ааронсон с помощью квантовых методов доказал, что перманент является #P-жестким.