Вычисление постоянного - Computing the permanent

В линейная алгебра, то вычисление постоянный из матрица это проблема, которая считается более сложной, чем вычисление детерминант матрицы, несмотря на кажущееся сходство определений.

Перманент определяется аналогично определителю как сумма произведений наборов элементов матрицы, лежащих в различных строках и столбцах. Однако если определитель взвешивает каждый из этих продуктов со знаком ± 1 на основе паритетность множества, перманент весит их всех знаком +1.

Хотя определитель можно вычислить в полиномиальное время к Гауссово исключение, обычно считается, что перманент нельзя вычислить за полиномиальное время. В теория сложности вычислений, Теорема Доблести утверждает, что вычисление перманентов # P-hard, и даже # P-complete для матриц, в которых все записи 0 или 1 Доблестный (1979). Это помещает вычисление перманента в класс задач, которые, как считается, вычислить еще сложнее, чем НП. Известно, что вычисление перманента невозможно для однородного по пространству журнала АКК⁰ схемы. (Аллендер и Гор 1994 )

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

Определение и наивный алгоритм

Перманент п-к-п матрица А = (а_{я, j}) определяется как

${\displaystyle \operatorname {perm} (A)=\sum _{\sigma \in S_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}.}$

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

Формула Райзера

Самый известный^[1] общий точный алгоритм обусловлен Х. Дж. Райзер  (1963 ). Метод Райзера основан на включение – исключение формула, которая может быть дана^[2] следующим образом: Пусть ${\displaystyle A_{k}}$ быть полученным от А удалив k колонны, пусть ${\displaystyle P(A_{k})}$ быть произведением строковых сумм ${\displaystyle A_{k}}$, и разреши ${\displaystyle \Sigma _{k}}$ быть суммой значений ${\displaystyle P(A_{k})}$ по всем возможным ${\displaystyle A_{k}}$. потом

${\displaystyle \operatorname {perm} (A)=\sum _{k=0}^{n-1}(-1)^{k}\Sigma _{k}.}$

Его можно переписать в терминах элементов матрицы следующим образом^[3]

${\displaystyle \operatorname {perm} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}.}$

Формулу Райзера можно вычислить с помощью ${\displaystyle O(2^{n-1}n^{2})}$ арифметические операции, или ${\displaystyle O(2^{n-1}n)}$ путем обработки наборов ${\displaystyle S}$ в Код Грея порядок.^[4]

Формула Баласубраманиана – Бакса – Франклина – Глинна

Другая формула, которая кажется такой же быстрой, как у Райзера (или, возможно, даже вдвое быстрее), содержится в двух кандидатских диссертациях. диссертации; видеть (Баласубраман, 1980 г. ), (Bax 1998 ); также(Бакс и Франклин 1996 ). Методы нахождения формулы совершенно разные, они связаны с комбинаторикой алгебры Мюра и с теорией конечных разностей соответственно. Другой способ, связанный с теорией инвариантов, - через поляризационная идентичность для симметричный тензор (Глинн 2010 ). Формула обобщается на бесконечно много других, как обнаружено всеми этими авторами, хотя неясно, быстрее ли они, чем основная. Видеть (Глинн 2013 ).

Простейшая известная формула этого типа (когда характеристика поля не равна двум):

${\displaystyle \operatorname {perm} (A)={\frac {1}{2^{n-1}}}\left[\sum _{\delta }\left(\prod _{k=1}^{n}\delta _{k}\right)\prod _{j=1}^{n}\sum _{i=1}^{n}\delta _{i}a_{ij}\right],}$

где внешняя сумма по всем ${\displaystyle 2^{n-1}}$ векторов ${\displaystyle \delta =(\delta _{1}=1,\delta _{2},\dots ,\delta _{n})\in \{\pm 1\}^{n}}$.

Особые случаи

Планарный и K_3,3-свободный

Количество идеальное соответствие в двудольный граф считается перманентом графа матрица двойственности, а перманент любой матрицы 0-1 может быть интерпретируется таким образом как количество точных совпадений на графике. За планарные графы (независимо от двудольности) Алгоритм FKT вычисляет количество точных совпадений за полиномиальное время, изменяя знаки тщательно выбранного подмножества записей в Матрица Тутте графика, так что Пфаффиан итоговых кососимметричная матрица (в квадратный корень своего детерминант ) - количество точных совпадений. Этот метод можно обобщить на графы, не содержащие подграфов. гомеоморфный к полный двудольный граф K_3,3.^[5]

Георгий Полиа задал вопрос^[6] о том, когда можно изменить знаки некоторых элементов матрицы 01 01 так, чтобы определитель новой матрицы был перманентом матрицы А. Не все матрицы 01 "конвертируемы" таким образом; на самом деле известно (Маркус и Минк (1961) ) что нет линейного отображения ${\displaystyle T}$ такой, что ${\displaystyle \operatorname {per} \,T(A)=\det A}$ для всех ${\displaystyle n\times n}$ матрицы ${\displaystyle A}$. Характеристика "конвертируемых" матриц была дана следующим образом: Маленький (1975) который показал, что такие матрицы - это в точности те, которые являются матрицей двойственности двудольных графов, которые имеют Пфаффовская ориентация: такая ориентация краев, что для каждого четного цикла ${\displaystyle C}$ для которого ${\displaystyle G\setminus C}$ имеет идеальное совпадение, имеется нечетное количество ребер, направленных вдоль C (и, следовательно, нечетное число с противоположной ориентацией). Также было показано, что это именно те графы, которые не содержат подграф, гомеоморфный ${\displaystyle K_{3,3}}$, как указано выше.

Вычисление по модулю числа

По модулю 2, перманент такой же, как определитель, поскольку ${\displaystyle (-1)\equiv 1{\pmod {2}}.}$ Его также можно вычислить по модулю ${\displaystyle 2^{k}}$ во время ${\displaystyle O(n^{4k-3})}$ за ${\displaystyle k\geq 2}$. Однако это UP-жесткий для вычисления перманента по модулю любого числа, не являющегося степенью двойки. Доблестный (1979)

Существуют различные формулы, представленные Глинн (2010) для вычисления по простому модулю пВо-первых, это метод, использующий символьные вычисления с частными производными.

Во-вторых, для п = 3 есть следующая формула для nxn-матрицы ${\displaystyle A}$с участием главногонесовершеннолетние (Коган (1996) ):

${\displaystyle \operatorname {per} (A)=(-1)^{n}\Sigma _{J\subseteq \{1,\dots ,n\}}\det(A_{J})\det(A_{\bar {J}}),}$

куда ${\displaystyle A_{J}}$ является подматрицей ${\displaystyle A}$ индуцированные строками и столбцами ${\displaystyle A}$проиндексировано ${\displaystyle J}$, и ${\displaystyle {\bar {J}}}$ является дополнением ${\displaystyle J}$ в ${\displaystyle \{1,\dots ,n\}}$, а определитель пустой подматрицы определен равным 1.

(На самом деле это разложение можно обобщить на произвольное характеристика p как следующую пару дуальных тождеств:

${\displaystyle \operatorname {per} (A)=(-1)^{n}\Sigma _{{J_{1}},...,{J_{p-1}}}\det(A_{J_{1}})...\det(A_{J_{p-1}})}$

${\displaystyle \operatorname {det} (A)=(-1)^{n}\Sigma _{{J_{1}},...,{J_{p-1}}}\operatorname {per} (A_{J_{1}})...\operatorname {per} (A_{J_{p-1}})}$

где в обеих формулах сумма берется по всем (p-1) -наборам ${\displaystyle {J_{1}},...,{J_{p-1}}}$ которые являются разделами множества ${\displaystyle \{1,\dots ,n\}}$ на p-1 подмножество, некоторые из них, возможно, пусты.

Первая формула имеет аналог гафниана симметричной ${\displaystyle A}$ и нечетный p:

${\displaystyle \operatorname {haf} ^{2}(A)=(-1)^{n}\Sigma _{{J_{1}},...,{J_{p-1}}}\det(A_{J_{1}})...\det(A_{J_{p-1}})(-1)^{|J_{1}|+...+|J_{(p-1)/2}|}}$

с суммой, взятой по тому же набору индексов. Более того, в характеристика нулевое аналогичное выражение суммы свертки, включающее как перманент, так и определитель, дает Гамильтонов цикл полином (определяется как ${\displaystyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$ куда ${\displaystyle {H_{n}}}$ - множество n-перестановок, имеющих только один цикл):${\displaystyle \operatorname {ham} (A)=\Sigma _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {per} (A_{\bar {J}})(-1)^{|J|}}$ . В характеристика 2 последнее равенство превращается в ${\displaystyle \operatorname {ham} (A)=\Sigma _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {det} (A_{\bar {J}})}$ что, таким образом, дает возможность полиномиально вычислить Гамильтонов цикл многочлен любого унитарный ${\displaystyle U}$ (т.е. такие, что ${\displaystyle U^{T}U=I}$ куда ${\displaystyle I}$ является единичной nxn-матрицей), поскольку каждый минор такой матрицы совпадает со своим алгебраическим дополнением: ${\displaystyle \operatorname {ham} (U)=\operatorname {det} ^{2}(U+I_{/1})}$ куда ${\displaystyle I_{/1}}$ является единичной nxn-матрицей, в которой индекс 1,1 заменен на 0. Более того, она, в свою очередь, может быть дополнительно обобщена для унитарный nxn-матрица ${\displaystyle U}$ в качестве ${\displaystyle \operatorname {ham_{K}} (U)=\operatorname {det} ^{2}(U+I_{/K})}$ куда ${\displaystyle K}$ является подмножеством {1, ..., n}, ${\displaystyle I_{/K}}$ - единичная nxn-матрица, в которой элементы индексов k, k заменены на 0 для всех k, принадлежащих ${\displaystyle K}$, и мы определяем ${\displaystyle \operatorname {ham_{K}} (A)=\sum _{\sigma \in H_{n}{(K)}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$ куда ${\displaystyle {H_{n}{(K)}}}$ - множество n-перестановок, каждый цикл которых содержит хотя бы один элемент ${\displaystyle K}$.)

Из этой формулы вытекают следующие тождества над полями характеристика 3:

для любого обратимый ${\displaystyle A}$

${\displaystyle \operatorname {per} (A^{-1})\operatorname {det} ^{2}(A)=\operatorname {per} (A)}$;

для любого унитарный ${\displaystyle U}$ , т.е. квадратная матрица ${\displaystyle U}$ такой, что ${\displaystyle U^{T}U=I\,}$ куда ${\displaystyle I}$ - единичная матрица соответствующего размера,

${\displaystyle \operatorname {per} ^{2}(U)=\det(U+V)\det(-U)}$

куда ${\displaystyle V}$ матрица, элементами которой являются кубы соответствующих элементов матрицы ${\displaystyle U}$.

Также было показано (Коган (1996) ), что, если мы определим квадратную матрицу ${\displaystyle A}$ как k-полуунитарный, когда ${\displaystyle rank(A^{T}A-I\,)}$ = kперманент 1-полуунитарной матрицы вычислим за полиномиальное время над полями характеристика 3, а для k > 1 проблема становится # 3-П-полный. (Параллельная теория касается Гамильтонов цикл многочлен от характеристика 2: хотя вычисление его на унитарных матрицах возможно за полиномиальное время, проблема является # 2-P-полной для k-полуунитарных матриц для любого k> 0). Последний результат был существенно расширен в 2017 г. (Кнежевич и Коэн (2017) ) и было доказано, что в характеристика 3 есть простая формула, связывающая перманенты квадратной матрицы и ее частичной обратной (для ${\displaystyle A_{11}}$ и ${\displaystyle A_{22}}$ будучи квадратным, ${\displaystyle A_{11}}$ существование обратимый ):

${\displaystyle \operatorname {per} \left({\begin{matrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{matrix}}\right)=\operatorname {det} ^{2}\left(A_{11}\right)\operatorname {per} \left({\begin{matrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{matrix}}\right)}$

и это позволяет за полиномиальное время сократить вычисление перманента матрицы размером nxn с подмножеством из k или k-1 строк, выражаемых как линейные комбинации другого (непересекающегося) подмножества из k строк, до вычисления перманента из ( nk) x (nk) - или (n-k + 1) x (n-k + 1) -матрица соответственно, поэтому введен оператор сжатия (аналогичный гауссовской модификации, применяемой для вычисления определителя), который «сохраняет» постоянный в характеристика 3. (Аналогично, стоит отметить, что Гамильтонов цикл многочлен от характеристика 2 также обладает своими инвариантными матричными сжатиями с учетом того факта, что ham (A) = 0 для любой nxn-матрицы A, имеющей три равных строки, или, если n> 2, пару индексов i, j, таких, что ее i -я и j-я строки идентичны, и его i-й и j-й столбцы также идентичны.) Закрытие этого оператора определяется как предел его последовательного применения вместе с преобразованием транспонирования (используется каждый раз, когда оператор покидает матрица без изменений) также является отображением оператора, когда применяется к классам матриц, один класс к другому. Тогда как оператор сжатия отображает класс 1-полуунитарных матриц в себя и классы унитарный и 2-полуунитарные, сжатие-замыкание 1-полуунитарного класса (а также класса матриц, полученных из унитарный единиц путем замены одной строки на произвольный вектор-строку - перманент такой матрицы есть, с помощью разложения Лапласа, сумма перманентов 1-полуунитарных матриц и, соответственно, вычислимая за полиномиальное время) пока неизвестна и напряженно связанных с общей проблемой вычислительной сложности перманента в характеристика 3 и главный вопрос P против NP: как было показано в (Кнежевич и Коэн (2017) ), если такое сжатие-замыкание представляет собой набор всех квадратных матриц над полем характеристика 3 или, по крайней мере, содержит матричный класс, на котором вычисляется перманент. # 3-П-полный (как и класс 2-полуунитарных матриц), то перманент вычислим за полиномиальное время в этом характеристика.

Кроме того, проблема поиска и классификации возможных аналогов постоянно сохраняющих компрессий, существующих в характеристика 3 для других простых характеристик сформулировано (Кнежевич и Коэн (2017) ), давая следующее тождество для матрицы размера nxn ${\displaystyle A}$ и два n-вектора (все их элементы из набора {0, ..., p-1}) ${\displaystyle \alpha }$ и ${\displaystyle \beta }$ такой, что ${\displaystyle {\sum _{i=1}^{n}\alpha _{i}}={\sum _{j=1}^{n}\beta _{j}}}$, справедливые в произвольном простом числе характеристика п:

${\displaystyle \operatorname {per} (A^{\left(\alpha ,\beta \right)})=\operatorname {det} ^{p-1}(A)\operatorname {per} \left(A^{-1}\right)^{\left((p-1\right){\vec {1}}_{n}-\beta ,\left(p-1\right){\vec {1}}_{n}-\alpha )}(\prod _{i=1}^{n}\alpha _{i}!)(\prod _{j=1}^{n}\beta _{j}!)\left(-1\right)^{n+\sum _{i=1}^{n}\alpha _{i}}}$

где для nxm-матрицы ${\displaystyle M}$, n-вектор ${\displaystyle x}$ и m-вектор ${\displaystyle y}$, оба вектора имеют все свои элементы из набора {0, ..., p-1}, ${\displaystyle M^{(x,y)}}$ обозначает матрицу, полученную от ${\displaystyle M}$ через повторение ${\displaystyle x_{i}}$ умножает на его i-ю строку для i = 1, ..., n и ${\displaystyle y_{j}}$ умножить на его j-й столбец для j = 1, ..., m (если кратность некоторой строки или столбца равна нулю, это будет означать, что строка или столбец были удалены, и, таким образом, это понятие является обобщением понятия подматрицы), и ${\displaystyle {\vec {1}}_{n}}$ обозначает n-вектор, все элементы которого равны единице. Это тождество является точным аналогом классической формулы, выражающей минор матрицы через минор ее инверсии, и, следовательно, демонстрирует (еще раз) своего рода двойственность между определителем и перманентом как относительными имманантами. (Собственно собственный аналог гафниана симметричной ${\displaystyle A}$ и нечетное простое число p равно ${\displaystyle \operatorname {haf} ^{2}(A^{\left(\alpha ,\alpha \right)})=\operatorname {det} ^{p-1}(A)\operatorname {haf} ^{2}\left(A^{-1}\right)^{\left((p-1\right){\vec {1}}_{n}-\alpha ,\left(p-1\right){\vec {1}}_{n}-\alpha )}(\prod _{i=1}^{n}\alpha _{i}!)^{2}(-1)^{n(p-1)/2+n+\sum _{i=1}^{n}\alpha _{i}}}$ ).

И, как еще более широкое обобщение для частичного обратного случая в простом числе характеристика p, для ${\displaystyle A_{11}}$, ${\displaystyle A_{22}}$ будучи квадратным, ${\displaystyle A_{11}}$ существование обратимый и размер ${\displaystyle {n_{1}}}$Икс${\displaystyle {n_{1}}}$, и ${\displaystyle {\sum _{i=1}^{n}\alpha _{i}}={\sum _{j=1}^{n}\beta _{j}}}$, выполняется также тождество

${\displaystyle \operatorname {per} \left({\begin{matrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{matrix}}\right)^{\left(\alpha ,\beta \right)}=\operatorname {det} ^{p-1}(A_{11})\operatorname {per} \left({\begin{matrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{matrix}}\right)^{\left((p-1\right){\vec {1}}_{n}-\beta ,\left(p-1\right){\vec {1}}_{n}-\alpha )}(\prod _{i=1}^{n}\alpha _{1,i}!)(\prod _{j=1}^{n}\beta _{1,j}!)\left(-1\right)^{n_{1}+\sum _{i=1}^{n}\alpha _{1,i}}}$

где общие векторы кратности строки / столбца ${\displaystyle \alpha }$ и ${\displaystyle \beta }$ для матрицы ${\displaystyle A}$ генерировать соответствующие векторы кратности строки / столбца ${\displaystyle \alpha _{s}}$ и ${\displaystyle \beta _{t}}$, s, t = 1,2, для его блоков (то же самое ${\displaystyle A}$частичный обратный элемент в правой части равенства).

Приблизительный расчет

Когда записи А неотрицательны, перманент можно вычислить примерно в вероятностный полиномиальное время с точностью до εM, куда M - значение перманента, а ε> 0 произвольно. Другими словами, существует полностью полиномиальная схема рандомизированной аппроксимации (FPRAS) (Джеррам, Вигода и Синклер (2001) Ошибка harvtxt: нет цели: CITEREFJerrumVigodaSinclair2001 (помощь)).

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

Можно приблизительно подсчитать количество точных соответствий в графе с помощью самовосстановление постоянного, с использованием FPAUS в сочетании с хорошо известным сокращением от отбора проб до подсчета из-за Джеррам, доблестный и Вазирани (1986) Ошибка harvtxt: нет цели: CITEREFJerrumValiantVazirani1986 (помощь). Позволять ${\displaystyle M(G)}$ обозначают количество совершенных совпадений в ${\displaystyle G}$. Грубо говоря, для любого конкретного ребра ${\displaystyle e}$ в ${\displaystyle G}$, путем выборки множества совпадений в ${\displaystyle G}$ и подсчитывая, сколько из них совпадают в ${\displaystyle G\setminus e}$, можно получить оценку отношения ${\displaystyle \rho ={\frac {M(G)}{M(G\setminus e)}}}$. Номер ${\displaystyle M(G)}$ затем ${\displaystyle \rho M(G\setminus e)}$, куда ${\displaystyle M(G\setminus e)}$ можно аппроксимировать, применяя тот же метод рекурсивно.

Другой класс матриц, для которых перманент может быть вычислен приближенно, - это набор положительно-полуопределенные матрицы (теоретико-сложная задача приближения перманента таких матриц с точностью до мультипликативной ошибки считается открытой^[7]). Соответствующий рандомизированный алгоритм основан на модели выборка бозонов и использует инструменты, необходимые для квантовая оптика, чтобы представить перманент положительно-полуопределенных матриц как ожидаемое значение конкретной случайной величины. Последний затем аппроксимируется его выборочным средним.^[8] Этот алгоритм для некоторого набора положительно-полуопределенных матриц аппроксимирует их перманент за полиномиальное время с точностью до аддитивной ошибки, которая более надежна, чем стандартный классический алгоритм полиномиального времени Гурвица.^[9]

Примечания

1. По состоянию на 2008 г. см. Ремпала и Весоловски (2008) Ошибка harvtxt: нет цели: CITEREFRempalaWesolowski2008 (помощь)
2. ван Линт и Уилсон (2001) п. 99
3. CRC Краткая энциклопедия математики Ошибка harvtxt: нет цели: CITEREFCRC_Concise_Encyclopedia_of_Mat Mathematics (помощь)
4. Nijenhuis и Wilf (1978)
5. Маленький (1974), Вазирани (1988)
6. Поля (1913), Райх (1971)
7. См. Открытую проблему (4) на "Shtetl Optimized: знакомство некоторых британцев с P vs. NP".
8. Чахмахчян, Левон; Серф, Николас; Гарсия-Патрон, Рауль (2017). «Квантовый алгоритм для оценки перманента положительных полуопределенных матриц». Phys. Ред. А. 96 (2): 022329. arXiv:1609.02416. Bibcode:2017PhRvA..96b2329C. Дои:10.1103 / PhysRevA.96.022329.
9. Гурвиц, Леонид (2005). «О сложности смешанных дискриминантов и смежных проблемах». Математические основы компьютерных наук. Конспект лекций по информатике. 3618: 447–458. Дои:10.1007/11549345_39. ISBN  978-3-540-28702-5.

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

• Аллендер, Эрик; Гор, Вивек (1994), "Нижняя граница однородной схемы для перманента", SIAM Журнал по вычислениям, 23 (5): 1026–1049, CiteSeerX  10.1.1.51.3546, Дои:10.1137 / s0097539792233907

• Баласубраманян, К. (1980), Комбинаторика и диагонали матриц (PDF), Кандидат наук. Диссертация, Департамент статистики, Колледж Лойола, Мадрас, Индия, T073, Индийский статистический институт, Калькутта

• Бакс, Эрик (1998), Конечно-разностные алгоритмы для подсчета задач, Кандидат наук. Диссертация, 223, Калифорнийский технологический институт

• Бакс, Эрик; Франклин, Дж. (1996), Решето конечных разностей для вычисления постоянного, Caltech-CS-TR-96-04, Калифорнийский технологический институт

• Глинн, Дэвид Г. (2010), «Перманент квадратной матрицы», Европейский журнал комбинаторики, 31 (7): 1887–1891, Дои:10.1016 / j.ejc.2010.01.010

• Глинн, Дэвид Г. (2013), «Постоянные формулы Веронезе», Конструкции, коды и криптография, 68 (1–3): 39–47, Дои:10.1007 / s10623-012-9618-1

• Jerrum, M .; Sinclair, A .; Vigoda, E. (2001), "Алгоритм полиномиальной аппроксимации перманента матрицы с неотрицательными элементами", Proc. 33-й симпозиум по теории вычислений, стр. 712–721, Дои:10.1145/380752.380877, ISBN  978-1581133493, ECCC  TR00-079
• Марк Джеррам; Лесли Валиант; Виджай Вазирани (1986), «Случайная генерация комбинаторных структур из равномерного распределения», Теоретическая информатика, 43: 169–188, Дои:10.1016 / 0304-3975 (86) 90174-Х

• Коган, Григорий (1996), "Вычисление перманентов над полями характеристики 3: где и почему становится сложно", 37-й ежегодный симпозиум по основам компьютерных наук (FOCS '96): 108–114, Дои:10.1109 / SFCS.1996.548469, ISBN  0-8186-7594-2

• Кнежевич, Анна; Коэн, Грег (2017), Некоторые факты о перманентах в конечных характеристиках, arXiv:1710.01783, Bibcode:2017arXiv171001783K

• ван Линт, Якобус Хендрикус; Уилсон, Ричард Мишал (2001), Курс комбинаторики, ISBN  978-0-521-00601-9

• Литтл, К. Х. С. (1974), "Расширение метода Кастелейна перечисления 1-факторов плоских графов", в Holton, D. (ed.), Proc. 2-я Австралийская конф. Комбинаторная математика, Конспект лекций по математике, 403, Springer-Verlag, стр. 63–72.

• Литтл, К. Х. С. (1975), "Характеризация конвертируемых (0, 1) -матриц", Журнал комбинаторной теории, Серия B, 18 (3): 187–208, Дои:10.1016/0095-8956(75)90048-9

• Marcus, M .; Минк, Х. (1961), «Об отношении между детерминантом и перманентом», Иллинойсский журнал математики, 5 (3): 376–381, Дои:10.1215 / ijm / 1255630882

• Nijenhuis, Альберт; Уилф, Герберт С. (1978), Комбинаторные алгоритмы, Academic Press

• Поля, Г. (1913), "Aufgabe 424", Arch. Математика. Phys., 20 (3): 27

• Райх, Симеон (1971), «Еще одно решение старой проблемы pólya», Американский математический ежемесячный журнал, 78 (6): 649–650, Дои:10.2307/2316574, JSTOR  2316574

• Ремпала, Гжегож А .; Весоловски, Яцек (2008), Симметричные функционалы на случайных матрицах и задачах случайных совпадений, п. 4, ISBN  978-0-387-75145-0

• Райзер, Герберт Джон (1963), Комбинаторная математика, Математические монографии Каруса, т. 14, Математическая ассоциация Америки

• Вазирани, Виджай В. (1988), "Алгоритмы ЧПУ для вычисления числа точных совпадений в K_3,3-бесплатные графики и связанные с ними задачи », Proc. 1-й скандинавский семинар по теории алгоритмов (SWAT '88), Конспект лекций по информатике, 318, Springer-Verlag, стр. 233–242, Дои:10.1007/3-540-19487-8_27, HDL:1813/6700, ISBN  978-3-540-19487-3

• Валиант, Лесли Г. (1979), «Сложность вычисления постоянного», Теоретическая информатика, Эльзевьер, 8 (2): 189–201, Дои:10.1016/0304-3975(79)90044-6

• "Постоянный", CRC Краткая энциклопедия математики, Chapman & Hall / CRC, 2002 г.

дальнейшее чтение

• Барвинок, А. (2017), «Аппроксимация перманентов и гафнианов», Дискретный анализ, arXiv:1601.07518, Дои:10.19086 / da.1244.