В линейной алгебре , то вычисление перманентный из матрицы является проблемой , которая считается более сложным , чем при вычислении определителя матрицы , несмотря на кажущееся сходство определений.
Перманент определяется аналогично определителю как сумма произведений наборов элементов матрицы, лежащих в различных строках и столбцах. Однако, если определитель взвешивает каждый из этих продуктов со знаком ± 1 на основе четности набора , постоянный элемент взвешивает их все со знаком +1.
Хотя определитель можно вычислить за полиномиальное время методом исключения Гаусса , обычно считается, что перманент нельзя вычислить за полиномиальное время. В теории сложности вычислений , теорема Valiant утверждает , что вычисление перманента является # P-трудно , и даже # P-полной для матриц , в которых все элементы равны 0 или 1 Valiant (1979) . Это помещает вычисление перманента в класс задач, которые, как считается, вычислить еще сложнее, чем NP . Известно, что вычисление перманента невозможно для схем ACC 0, однородных по пространству журнала ( Allender & Gore 1994).)
Разработка как точных, так и приближенных алгоритмов вычисления перманента матрицы является активной областью исследований.
Определение и наивный алгоритм
Перманент в п матрицы с размерностью п матрица = ( I, J ) определяются как
Сумма здесь распространяется на все элементы σ симметрической группы S n , т.е. на все перестановки чисел 1, 2,…, n . Эта формула отличается от соответствующей формулы для определителя только тем, что в определителе каждое произведение умножается на знак перестановки σ, в то время как в этой формуле каждое произведение без знака. Формула может быть напрямую переведена в алгоритм, который наивно расширяет формулу, суммируя по всем перестановкам и в сумме, умножая каждую запись матрицы. Для этого требуется n! n арифметических операций.
Формула Райзера
Самый известный [1] общий точный алгоритм принадлежит HJ Ryser ( 1963 ). Метод Райзера основан на формуле включения-исключения, которую можно представить [2] следующим образом: Пустьполучится из A удалением k столбцов, пусть быть произведением строковых сумм , и разреши быть суммой значений по всем возможным . потом
Его можно переписать в терминах элементов матрицы следующим образом [3]
Формулу Райзера можно вычислить с помощью арифметические операции, или путем обработки наборов в порядке кода Грея . [4]
Формула Баласубраманиана – Бакса – Франклина – Глинна
Еще одну формулу, которая кажется такой же быстрой, как у Райзера (или, возможно, даже вдвое быстрее), можно найти у двух кандидатов наук. диссертации; см. ( Balasubramanian 1980 ), ( Bax 1998 ); также ( Bax & Franklin 1996 ). Методы нахождения формулы совершенно разные, они связаны с комбинаторикой алгебры Мюра и теорией конечных разностей соответственно. Другой путь, связанный с теорией инвариантов, - это поляризационное тождество для симметричного тензора ( Glynn 2010 ). Формула обобщается на бесконечно много других, как обнаружено всеми этими авторами, хотя неясно, быстрее ли они, чем базовая. См. ( Glynn 2013 ).
Простейшая известная формула этого типа (когда характеристика поля не равна двум):
где внешняя сумма по всем векторов .
Особые случаи
Планар и К 3,3 -свободный
Количество идеальных совпадений в двудольном графе подсчитывается с помощью перманента матрицы двойного сопряжения графа , а перманент любой матрицы 0-1 можно интерпретировать таким образом как количество идеальных совпадений в графе. Для плоских графов (независимо от двудольности) алгоритм FKT вычисляет количество точных сопоставлений за полиномиальное время, изменяя знаки тщательно выбранного подмножества элементов в матрице Тутте графа, так что пфаффиан результирующего перекоса - симметричная матрица ( квадратный корень из ее определителя ) - это количество точных совпадений. Этот метод может быть обобщен на графики , которые не содержат подграф гомеоморфных к полному двудольному графу K 3,3 . [5]
Джордж Полиа задал вопрос [6] о том, когда можно изменить знаки некоторых элементов матрицы 01 A так, чтобы определитель новой матрицы был перманентом матрицы A. Не все матрицы 01 являются "конвертируемыми" таким образом; на самом деле известно ( Marcus & Minc (1961) ), что не существует линейной карты такой, что для всех матрицы . Характеристика "конвертируемых" матриц была дана Литтлом (1975), который показал, что такие матрицы - это в точности те, которые являются матрицей взаимосопряженности двудольных графов, которые имеют ориентацию Пфаффа : ориентация ребер такая, что для каждого четного цикла для которого имеет полное совпадение, имеется нечетное количество ребер, направленных вдоль C (и, следовательно, нечетное число с противоположной ориентацией). Также было показано, что это именно те графы, которые не содержат подграфа, гомеоморфного, как указано выше.
Вычисление по модулю числа
По модулю 2 перманент совпадает с определителем, поскольку Его также можно вычислить по модулю во время для . Однако очень сложно вычислить перманент по модулю любого числа, не являющегося степенью 2. Valiant (1979)
Глинн (2010) приводит различные формулы для вычисления по простому модулю p . Во-первых, есть символьные вычисления с частными производными.
Во-вторых, для p = 3 есть следующая формула для n × n-матрицыс участием главных миноров матрицы ( Коган (1996) ):
где является подматрицей индуцированные строками и столбцами проиндексировано , а также является дополнением в , а определитель пустой подматрицы равен 1.
Приведенное выше разложение можно обобщить на произвольную характеристику p как следующую пару двойственных тождеств:
где в обеих формулах сумма берется по всем (p-1) -наборам которые являются перегородками множества на p-1 подмножество, некоторые из них, возможно, пусты.
Первая формула имеет аналог гафниана симметричной и нечетный p:
с суммой, взятой по тому же набору индексов. Более того, в нулевой характеристике аналогичное выражение суммы свертки, включающее как перманент, так и определитель, дает полином гамильтонова цикла (определяемый как где - множество n-перестановок, имеющих только один цикл):
Из этой формулы вытекают следующие тождества над полями характеристики 3:
для любого обратимого
для любого унитарного , т.е. квадратная матрица такой, что где - единичная матрица соответствующего размера,
где матрица, элементами которой являются кубики соответствующих элементов матрицы .
Также было показано ( Kogan (1996) ), что если мы определим квадратную матрицу как k-полуунитарный, когда , перманент 1-полуунитарной матрицы вычислим за полиномиальное время над полями характеристики 3, а при k > 1 задача становится # 3-P-полной . (Параллельная теория касается полинома гамильтонова цикла в характеристике 2: хотя вычисление его на унитарных матрицах возможно за полиномиальное время, проблема # 2-P-полная для k-полуунитарных матриц для любого k > 0). Последний результат был существенно расширен в 2017 г. ( Knezevic & Cohen (2017) ), и было доказано, что в характеристике 3 есть простая формула, связывающая перманенты квадратной матрицы и ее частичного обратного (для а также будучи квадратным, быть обратимым ):
и это позволяет за полиномиальное время сократить вычисление перманента матрицы размера n × n с подмножеством из k или k −1 строк, выражаемых как линейные комбинации другого (непересекающегося) подмножества из k строк, до вычисления перманента ( n - k ) × ( n - k ) - или ( n - k +1) × ( n - k +1) -матрица соответственно, поэтому введя оператор сжатия (аналогично гауссовской модификации, применяемой для вычисления определителя ), который «сохраняет» перманент в характеристике 3. (Аналогично, стоит отметить, что многочлен гамильтонова цикла в характеристике 2 также обладает своими инвариантными матричными сжатиями, учитывая тот факт, что ham ( A ) = 0 для любого n × n -матрица A, имеющая три равные строки или, если 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 :
где для n × m -матрицы, n-вектор и m-вектор , оба вектора имеют все элементы из множества {0,…, p −1}, обозначает матрицу, полученную от через повторение умножить на его i -ю строку для i = 1,…, n иумножить на его j -й столбец для j = 1,…, m (если кратность некоторой строки или столбца равна нулю, это будет означать, что строка или столбец были удалены, и, таким образом, это понятие является обобщением понятия подматрицы), иобозначает n-вектор, все элементы которого равны единице. Это тождество является точным аналогом классической формулы, выражающей минор матрицы через минор ее инверсии, и, следовательно, демонстрирует (еще раз) своего рода двойственность между определителем и перманентом как относительными имманантами. (Собственно собственный аналог гафниана симметричной и нечетное простое число p равно ).
И, как еще более широкое обобщение для частичного обратного случая в простой характеристике p, для , будучи квадратным, быть обратимым и иметь размерИкс, а также , выполняется также тождество
где общие векторы кратности строки / столбца а также для матрицы генерировать соответствующие векторы кратности строки / столбца а также , s, t = 1,2, для его блоков (то же самое частичный обратный элемент в правой части равенства).
Приблизительный расчет
Когда элементы A неотрицательны, перманент может быть вычислен приблизительно за вероятностное полиномиальное время с точностью до ε M , где M - значение перманента, а ε> 0 - произвольно. Другими словами, существует полностью полиномиальная схема рандомизированной аппроксимации (FPRAS) ( Jerrum, Vigoda & Sinclair (2001)
).Самым сложным шагом в вычислениях является построение алгоритма для почти однородной выборки из множества всех совершенных сопоставлений в данном двудольном графе: другими словами, полностью полиномиальный почти однородный выборщик (FPAUS). Это можно сделать с помощью алгоритма Монте-Карло цепи Маркова, который использует правило Метрополиса для определения и запуска цепи Маркова , распределение которой близко к равномерному, а время перемешивания полиномиально.
Можно приблизительно подсчитать количество точных совпадений на графике посредством самовосстановления перманента, используя FPAUS в сочетании с хорошо известным сокращением от выборки к подсчету, благодаря Джерруму, Валианту и Вазирани (1986). обозначают количество совершенных совпадений в . Грубо говоря, для любого конкретного ребра в , путем выборки множества совпадений в и подсчитывая, сколько из них совпадают в , можно получить оценку отношения . Номер затем , где можно аппроксимировать, применяя тот же метод рекурсивно.
. ПозволятьДругой класс матриц, для которых перманент может быть вычислен приближенно, - это набор положительно-полуопределенных матриц (теоретико-сложная задача аппроксимации перманента таких матриц с точностью до мультипликативной ошибки считается открытой [7] ). Соответствующий рандомизированный алгоритм основан на модели отбора бозонов и использует инструменты, свойственные квантовой оптике , для представления перманента положительно-полуопределенных матриц как ожидаемого значения конкретной случайной величины. Последний затем аппроксимируется его выборочным средним. [8] Этот алгоритм для некоторого набора положительно-полуопределенных матриц аппроксимирует их перманент за полиномиальное время с точностью до аддитивной ошибки, которая более надежна, чем алгоритм стандартного классического полиномиального алгоритма Гурвица. [9]
Заметки
- ^ В 2008, см Rempala & Wesolowski (2008)
- ^ van Lint & Wilson (2001) стр. 99
- ^ CRC Краткая энциклопедия математики
- ^ Nijenhuis & Уилф (1978)
- ^ Литтл (1974) , Вазирани (1988)
- ^ Полиа (1913) , Reich (1971)
- ^ См. Открытую проблему (4) в «Shtetl Optimized: Знакомство некоторых британцев с P vs. NP» .
- ^ Чахмахчян, Левон; Серф, Николас; Гарсия-Патрон, Рауль (2017). «Квантовый алгоритм для оценки перманента положительных полуопределенных матриц». Phys. Rev. A . 96 (2): 022329. arXiv : 1609.02416 . Bibcode : 2017PhRvA..96b2329C . DOI : 10.1103 / PhysRevA.96.022329 . S2CID 54194194 .
- ^ Гурвиц, Леонид (2005). «О сложности смешанных дискриминантов и смежных проблемах». Математические основы информатики . Конспект лекций по информатике. 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), "Постоянные формулы из Veronesean", Designs, коды и криптография , 68 (1-3): 39-47, DOI : 10.1007 / s10623-012-9618-1 , S2CID 36911503
- Jerrum, M .; Sinclair, A .; Vigoda, E. (2001), "Алгоритм полиномиального приближения для перманента матрицы с неотрицательными элементами", Proc. 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: где и почему становится трудно», тридцать седьмым ежегодный симпозиум по Основе информатики (РПДА '96) : 108-114, да : 10.1109 / SFCS.1996.548469 , ISBN 0-8186-7594-2, S2CID 39024286
- Кнежевич, Анна; Коэн, Грег (2017), Некоторые факты о перманентах в конечных характеристиках , arXiv : 1710.01783 , Bibcode : 2017arXiv171001783K
- ван Линт, Якобус Хендрикус; Уилсон, Ричард Мишель (2001), курс комбинаторики , ISBN 978-0-521-00601-9
- Литтл, CHC (1974), "Расширение метода Кастелейна перечисления 1-факторов плоских графов", в Holton, D. (ed.), Proc. 2-я Австралийская конф. Комбинаторная математика , Конспект лекций по математике, 403 , Springer-Verlag, стр. 63–72.
- Маленький, CHC (1975), "Характеристика конвертируемых (0, 1) -матрицы", Журнал комбинаторной теории , Series B, 18 (3): 187-208, DOI : 10,1016 / 0095-8956 (75) 90048- 9
- Marcus, M .; Минк, Х. (1961), "О соотношении между детерминанта и перманента", штат Иллинойс Журнал математики , 5 (3): 376-381, DOI : 10,1215 / IJM / 1255630882
- Nijenhuis, Альберт; Уилф, Герберт С. (1978), комбинаторные алгоритмы , Academic Press
- Pólya, G. (1913), "Aufgabe 424", Arch. Математика. Phys. , 20 (3): 27
- Reich, Симеон (1971), "Еще одно решение старой проблемы Полна", American Mathematical Monthly , 78 (6): 649-650, DOI : 10,2307 / 2316574 , JSTOR 2316574
- Rempała, Grzegorz A .; Весоловски, Яцек (2008), Симметричные функционалы на случайных матрицах и проблемы случайных совпадений , с. 4, ISBN 978-0-387-75145-0
- Райзер, Герберт Джон (1963), Комбинаторная математика , Математические монографии Карус, Vol. 14, Математическая ассоциация Америки
- Вазирани, Виджай В. (1988), "Алгоритмы ЧПУ для вычисления числа совершенных паросочетаний в K 3,3 -свободных графах и связанные проблемы", Proc. Первый скандинавский семинар по теории алгоритмов (Спецназ '88) , Lecture Notes в области компьютерных наук, 318 , Springer-Verlag, стр 233-242,. DOI : 10.1007 / 3-540-19487-8_27 , ЛВП : 1813/6700 , ISBN 978-3-540-19487-3
- Valiant, Лесли Г. (1979), "Сложность вычисления перманента", Теоретическая информатика , Elsevier, 8 (2): 189-201, DOI : 10,1016 / 0304-3975 (79) 90044-6
- "Постоянный", CRC Concise Encyclopedia of Mathematics , Chapman & Hall / CRC, 2002
дальнейшее чтение
- Барвинок, А. (2017), «Аппроксимация перманентов и гафнианов», Дискретный анализ , arXiv : 1601.07518 , doi : 10.19086 / da.1244 , S2CID 397350.