Вычисление постоянного

Задача по линейной алгебре

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

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

В то время как определитель может быть вычислен за полиномиальное время методом исключения Гаусса , обычно считается, что перманент не может быть вычислен за полиномиальное время. В теории сложности вычислений теорема Вэлианта утверждает, что вычисление перманентов является #P-трудным , и даже #P-полным для матриц, в которых все элементы равны 0 или 1 Вэлиант (1979). Это помещает вычисление перманента в класс задач, которые считаются еще более сложными для вычисления, чем NP . Известно, что вычисление перманента невозможно для однородных по логарифмическому пространству схем ACC ^{0. (Allender & Gore 1994)}

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

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

Перманент матрицы A = ( a _i,j ) размером n на n определяется как

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

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

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

Самый известный ^[1] общий точный алгоритм принадлежит HJ Ryser  (1963). Метод Ryser основан на формуле включения-исключения , которая может быть задана ^[2] следующим образом: Пусть будет получено из A путем удаления k столбцов, пусть будет произведением строковых сумм , и пусть будет суммой значений по всем возможным . Тогда ${\displaystyle A_{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}.}$

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

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

Другая формула, которая, по-видимому, так же быстра, как и формула Райзера (или, возможно, даже в два раза быстрее), находится в двух докторских диссертациях; см. (Balasubramanian 1980), (Bax 1998); а также (Bax & Franklin 1996). Методы нахождения формулы совершенно различны, поскольку связаны с комбинаторикой алгебры Мьюира и теорией конечных разностей соответственно. Другой способ, связанный с теорией инвариантов, — через тождество поляризации для симметричного тензора (Glynn 2010). Формула обобщается на бесконечное множество других, как было найдено всеми этими авторами, хотя неясно, быстрее ли они, чем базовая. См. (Glynn 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}}$

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

Плоские иК3,3-бесплатно

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

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

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

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

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

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

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

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

Приведенное выше разложение можно обобщить в произвольной характеристике p как следующую пару дуальных тождеств: где в обеих формулах сумма берется по всем ( p − 1)-кортежам , которые являются разбиениями множества на p − 1 подмножеств, некоторые из которых, возможно, пусты. $${\displaystyle {\begin{aligned}\operatorname {per} (A)&=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\det(A_{J_{1}})\dotsm \det(A_{J_{p-1}})\\\det(A)&=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\operatorname {per} (A_{J_{1}})\dotsm \operatorname {per} (A_{J_{p-1}})\end{aligned}}}$$ ${\displaystyle {J_{1}},\ldots ,{J_{p-1}}}$ ${\displaystyle \{1,\dots ,n\}}$

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

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

с суммой, взятой по тому же набору индексов. Более того, в нулевой характеристике аналогичное выражение суммы свертки, включающее как перманент, так и определитель, дает полином гамильтонового цикла (определяемый как, где — множество n-перестановок, имеющих только один цикл): ${\textstyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$ ${\displaystyle H_{n}}$ $${\displaystyle \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {per} (A_{\bar {J}})(-1)^{|J|}.}$$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Когда элементы A неотрицательны, перманент может быть приблизительно вычислен за вероятностное полиномиальное время с точностью до ε M , где M — значение перманента, а ε > 0 — произвольно. Другими словами, существует полностью полиномиальная рандомизированная схема приближения (FPRAS) (Jerrum, Sinclair & Vigoda (2001)).

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

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

Другой класс матриц, для которых перманент представляет особый интерес, — это положительно-полуопределенные матрицы . ^[7] Используя технику подсчета Стокмейера, их можно вычислить в пределах класса , но в целом это считается невыполнимым классом. Аппроксимировать перманенты матриц PSD в пределах субэкспоненциального множителя NP-трудно, и предполагается, что это -трудно ^[8] Если наложить дополнительные ограничения на спектр , известны более эффективные алгоритмы. Один рандомизированный алгоритм основан на модели выборки бозонов и использует инструменты, присущие квантовой оптике , для представления перманента положительно-полуопределенных матриц как ожидаемого значения определенной случайной величины. Последняя затем аппроксимируется ее выборочным средним. ^[9] Этот алгоритм для определенного набора положительно-полуопределенных матриц аппроксимирует их перманент за полиномиальное время с точностью до аддитивной ошибки, что более надежно, чем у стандартного классического алгоритма полиномиального времени Гурвица. ^[10] ${\displaystyle {\textsf {BPP}}^{\textsf {NP}}}$ ${\displaystyle {\textsf {BPP}}^{\textsf {NP}}}$

Примечания

1. По состоянию на 2008 год см. Rempala & Wesolowski (2008)
2. ван Линт и Уилсон (2001), с. 99
3. CRC Краткая энциклопедия математики
4. Нийенхейс и Вильф (1978)
5. Литтл (1974), Вазирани (1988)
6. Полиа (1913), Рейх (1971)
7. См. открытую задачу (4) в Shtetl Optimized: Знакомство некоторых британцев с P против NP, 22 июля 2015 г.
8. Мейбург, Александр (2023), «Неаппроксимируемость положительных полуопределенных постоянных и квантовая томография состояний», Algorithmica , 85 (12): 3828–3854, arXiv : 2111.03142 , doi : 10.1007/s00453-023-01169-1
9. Чахмахчян, Левон; Серф, Николас; Гарсия-Патрон, Рауль (2017), «Квантовый алгоритм для оценки перманента положительных полуопределенных матриц», Phys. Rev. A , 96 (2): 022329, arXiv : 1609.02416 , Bibcode : 2017PhRvA..96b2329C, doi : 10.1103/PhysRevA.96.022329, S2CID  54194194
10. Гурвиц, Леонид (2005), «О сложности смешанных дискриминантов и связанных с ними проблемах», Математические основы информатики 2005 , Lecture Notes in Computer Science, т. 3618, стр. 447–458, doi :10.1007/11549345_39, ISBN 978-3-540-28702-5

Ссылки

• Аллендер, Эрик; Гор, Вивек (1994), «Нижняя граница равномерной цепи для перманента», SIAM Journal on Computing , 23 (5): 1026–1049, CiteSeerX  10.1.1.51.3546 , doi :10.1137/s0097539792233907
• Баласубраманян, К. (1980), Комбинаторика и диагонали матриц (PDF) , докторская диссертация, кафедра статистики, колледж Лойола, Мадрас, Индия, том T073, Индийский статистический институт, Калькутта
• Бакс, Эрик (1998), Конечно-разностные алгоритмы для задач подсчета , докторская диссертация, т. 223, Калифорнийский технологический институт
• Бакс, Эрик; Франклин, Дж. (1996), Конечно-разностное решето для вычисления постоянного , Caltech-CS-TR-96-04, Калифорнийский технологический институт
• Глинн, Дэвид Г. (2010), «Перманент квадратной матрицы», Европейский журнал комбинаторики , 31 (7): 1887–1891, doi :10.1016/j.ejc.2010.01.010
• Глинн, Дэвид Г. (2013), «Постоянные формулы из Веронеза», Designs, Codes and Cryptography , 68 (1–3): 39–47, doi :10.1007/s10623-012-9618-1, S2CID  36911503
• Джеррум, М.; Синклер, А.; Вигода, Э. (2001), «Алгоритм аппроксимации полиномиальным временем для перманента матрицы с неотрицательными элементами», Труды 33-го симпозиума по теории вычислений , стр. 712–721, doi :10.1145/380752.380877, ISBN 978-1581133493, S2CID  8368245, ECCC  TR00-079
• Джеррум, Марк ; Валиант, Лесли ; Вазирани, Виджай (1986), «Случайная генерация комбинаторных структур из равномерного распределения», Теоретическая информатика , 43 : 169–188, doi :10.1016/0304-3975(86)90174-X
• Коган, Григорий (1996), «Вычисление перманентов над полями характеристики 3: где и почему это становится трудным», Труды 37-й конференции по основаниям информатики , стр. 108–114, doi :10.1109/SFCS.1996.548469, ISBN 0-8186-7594-2, S2CID  39024286
• Кнежевич, Анна; Коэн, Грег (2017), Некоторые факты о постоянных в конечных характеристиках , arXiv : 1710.01783 , Bibcode : 2017arXiv171001783K
• ван Линт, Якобус Хендрикус; Уилсон, Ричард Михейл (2001), Курс комбинаторики , Cambridge University Press, ISBN 978-0-521-00601-9
• Little, CHC (1974), «Расширение метода Кастелейна перечисления 1-факторов планарных графов», в Holton, D. (ред.), Proc. 2nd Australian Conf. Combinatori Mathematics , Lecture Notes in Mathematics, т. 403, Springer-Verlag, стр. 63–72
• Little, CHC (1975), «Характеристика конвертируемых (0, 1)-матриц», Журнал комбинаторной теории , Серия B, 18 (3): 187–208, doi :10.1016/0095-8956(75)90048-9
• Маркус, М.; Минк, Х. (1961), «О связи между определителем и перманентом», Illinois Journal of Mathematics , 5 (3): 376–381, doi : 10.1215/ijm/1255630882
• Нийенхейс, Альберт; Вильф, Герберт С. (1978), Комбинаторные алгоритмы , Academic Press
• Полиа, Г. (1913), "Aufgabe 424", Arch. Math. Phys. , 20 (3): 27
• Райх, Симеон (1971), «Еще одно решение старой проблемы полиа», American Mathematical Monthly , 78 (6): 649–650, doi :10.2307/2316574, JSTOR  2316574
• Ремпала, Гжегож А.; Весоловский, Яцек (2008), Симметричные функционалы на случайных матрицах и задачах случайного сопоставления , Springer, p. 4, ISBN 978-0-387-75145-0
• Райзер, Герберт Джон (1963), Комбинаторная математика , Математические монографии Каруса, том 14, Математическая ассоциация Америки , ISBN 978-1-61444-014-7
• Вазирани, Виджай В. (1988), «NC-алгоритмы для вычисления числа совершенных паросочетаний в графах, свободных от K _{3,3, и связанные с ними проблемы»,} Труды 1-го Скандинавского семинара по теории алгоритмов (SWAT '88) , Lecture Notes in Computer Science, т. 318, Springer-Verlag, стр. 233–242, doi :10.1007/3-540-19487-8_27, hdl : 1813/6700 , ISBN 978-3-540-19487-3
• Вэлиант, Лесли Г. (1979), «Сложность вычисления постоянного», Теоретическая информатика , 8 (2), Elsevier: 189–201, doi : 10.1016/0304-3975(79)90044-6, S2CID  1637832
• «Постоянный», CRC Краткая энциклопедия математики , Chapman & Hall/CRC, 2002

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

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