Výpočet trvalé - Computing the permanent

v lineární algebra, výpočet trvalý a matice je problém, o kterém se předpokládá, že je obtížnější než výpočet určující matice navzdory zjevné podobnosti definic.

Trvalý je definován podobně jako determinant, jako součet součinů sad položek matice, které leží v odlišných řádcích a sloupcích. Pokud však determinant váží každý z těchto produktů se znaménkem ± 1 na základě parita sady, trvalé je všechny váží se znaménkem +1.

Zatímco determinant lze vypočítat v polynomiální čas podle Gaussova eliminace, obecně se věří, že permanent nelze vypočítat v polynomiálním čase. v teorie výpočetní složitosti, věta Valiant uvádí, že výpočetní stálice je # P-tvrdé, a dokonce # P-kompletní pro matice, ve kterých jsou všechny položky 0 nebo 1 Valiant (1979). To staví výpočet permanentu do třídy problémů, o nichž se předpokládá, že je ještě obtížnější je vypočítat než NP. Je známo, že výpočet permanentního je pro logspace uniformní nemožný ACC⁰ obvodů. (Allender & Gore 1994 )

Aktivní oblastí výzkumu je vývoj přesných i přibližných algoritmů pro výpočet permanentu matice.

Definice a naivní algoritmus

Trvalý n-podle-n matice A = (A_{já, j}) je definován jako

${ displaystyle operatorname {perm} (A) = součet _ { sigma v S_ {n}} prod _ {i = 1} ^ {n} a_ {i, sigma (i)}.}$

Součet zde přesahuje všechny prvky σ z symetrická skupina S_ntj. nade vše obměny z čísel 1, 2, ..., n. Tento vzorec se liší od odpovídajícího vzorce pro determinant pouze v tom, že v determinantu je každý produkt vynásoben znak permutace σ zatímco v tomto vzorci je každý produkt nepodepsaný. Vzorec může být přímo přeložen do algoritmu, který naivně rozšiřuje vzorec, sčítá všechny permutace a v součtu vynásobí každou položku matice. To vyžaduje n! n aritmetické operace.

Ryserův vzorec

Nejznámější^[1] obecný přesný algoritmus je způsoben H. J. Ryser  (1963 ). Ryserova metoda je založena na začlenění – vyloučení vzorec, který lze uvést^[2] takto: Let ${ displaystyle A_ {k}}$ lze získat z A odstraněním k sloupce, nech ${ displaystyle P (A_ {k})}$ být součinem řádkových součtů ${ displaystyle A_ {k}}$a nechte ${ displaystyle Sigma _ {k}}$ být součtem hodnot ${ displaystyle P (A_ {k})}$ přes všechno možné ${ displaystyle A_ {k}}$. Pak

${ displaystyle operatorname {perm} (A) = součet _ {k = 0} ^ {n-1} (- 1) ^ {k} Sigma _ {k}.}$

Může být přepsán, pokud jde o položky matice, následovně^[3]

${ displaystyle operatorname {perm} (A) = (- 1) ^ {n} součet _ {S subseteq {1, tečky, n }} (- 1) ^ {| S |} prod _ {i = 1} ^ {n} součet _ {j v S} a_ {ij}.}$

Ryserův vzorec lze vyhodnotit pomocí ${ displaystyle O (2 ^ {n-1} n ^ {2})}$ aritmetické operace nebo ${ displaystyle O (2 ^ {n-1} n)}$ zpracováním sad ${ displaystyle S}$ v Šedý kód objednat.^[4]

Balasubramanian – Bax – Franklin – Glynn vzorec

Další vzorec, který se zdá být stejně rychlý jako Ryserův (nebo možná dokonce dvakrát rychlejší), lze nalézt ve dvou Ph.D. práce; viz (Balasubramanian 1980 ), (Bax 1998 ); taky(Bax & Franklin 1996 ). Metody k nalezení vzorce jsou zcela odlišné, souvisí s kombinatorikou Muirovy algebry a teorií konečných rozdílů. Dalším způsobem spojeným s invariantní teorií je pomocí polarizační identita pro symetrický tenzor (Glynn 2010 ). Vzorec zobecňuje na nekonečně mnoho dalších, jak zjistili všichni tito autoři, i když není jasné, zda jsou rychlejší než základní. Viz (Glynn 2013 ).

Nejjednodušší známý vzorec tohoto typu (pokud charakteristika pole není dvě) je

${ 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], }$

kde je vnější součet nade vše ${ displaystyle 2 ^ {n-1}}$ vektory ${ displaystyle delta = ( delta _ {1} = 1, delta _ {2}, tečky, delta _ {n}) in { pm 1 } ^ {n}}$.

Speciální případy

Rovinné a K._3,3-volný, uvolnit

Počet perfektní párování v bipartitní graf se počítá permanentem grafu biadjacency matice, a permanent libovolné matice 0-1 může být interpretován tímto způsobem jako počet dokonalých shody v grafu. Pro rovinné grafy (bez ohledu na bipartitu), Algoritmus FKT spočítá počet dokonalých shody v polynomiálním čase změnou znaků pečlivě vybrané podmnožiny položek v Tutte matrix grafu, takže Pfaffian výsledného šikmo symetrická matice (dále jen odmocnina jeho určující ) je počet perfektních shody. Tuto techniku ​​lze zobecnit na grafy, které neobsahují žádný podgraf homeomorfní do kompletní bipartitní graf K._3,3.^[5]

George Pólya položil otázku^[6] kdy je možné změnit znaménka některých záznamů matice 01 tak, aby determinant nové matice byl stálý A. Ne všechny matice 01 jsou tímto způsobem „konvertibilní“; ve skutečnosti je známo (Marcus & Minc (1961) ) neexistuje lineární mapa ${ displaystyle T}$ takhle ${ displaystyle operatorname {per} , T (A) = det A}$ pro všechny ${ displaystyle n krát n}$ matice ${ displaystyle A}$. Charakterizace „konvertibilních“ matic byla dána vztahem Malý (1975) který ukázal, že takové matice jsou přesně ty, které jsou maticí biadjacence bipartitních grafů, které mají Pfaffianská orientace: orientace hran tak, aby pro každý sudý cyklus ${ displaystyle C}$ pro který ${ displaystyle G setminus C}$ má perfektní shodu, existuje lichý počet hran směřujících podél C (a tedy liché číslo s opačnou orientací). Ukázalo se také, že tyto grafy jsou přesně ty, které neobsahují podgraf homeomorfní ${ displaystyle K_ {3,3}}$, jak je uvedeno výše.

Výpočet modulo číslo

Modulo 2, permanent je stejný jako determinant, jako ${ displaystyle (-1) equiv 1 { pmod {2}}.}$ Lze jej také vypočítat modulo ${ displaystyle 2 ^ {k}}$ včas ${ displaystyle O (n ^ {4k-3})}$ pro ${ displaystyle k geq 2}$. Ale je UP-hard vypočítat trvalé modulo jakékoli číslo, které není mocninou 2. Valiant (1979)

Existuje několik vzorců daných Glynn (2010) pro výpočet modulo prvočíslo pZa prvé existuje jeden, který používá symbolické výpočty s částečnými derivacemi.

Zadruhé, pro p = 3 existuje následující vzorec pro matici nxn ${ displaystyle A}$, zahrnující jistinu maticenezletilí (Kogan (1996) ):

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

kde ${ displaystyle A_ {J}}$ je submatice ${ displaystyle A}$ vyvolané řádky a sloupci ${ displaystyle A}$indexováno podle ${ displaystyle J}$, a ${ displaystyle { bar {J}}}$ je doplňkem ${ displaystyle J}$ v ${ displaystyle {1, tečky, n }}$, zatímco determinant prázdné podmatice je definován jako 1.

(Ve skutečnosti lze výše uvedenou expanzi zobecnit libovolně charakteristický p jako následující dvojice dvojích identit:

${ 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}})}$

kde v obou vzorcích je součet převzat za všechny (p-1) n-tice ${ displaystyle {J_ {1}}, ..., {J_ {p-1}}}$ to jsou oddíly sady ${ displaystyle {1, tečky, n }}$ do p-1 podmnožin, některé z nich mohou být prázdné.

Bývalý vzorec má analogii k hafnianovi symetrie ${ displaystyle A}$ a liché 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} |}}$

se součtem převzatým ze stejné sady indexů. Navíc v charakteristický nula podobný výraz konvolučního součtu zahrnující jak permanentní, tak determinantní výtěžek Hamiltonovský cyklus polynom (definováno jako ${ displaystyle operatorname {ham} (A) = součet _ { sigma v H_ {n}} prod _ {i = 1} ^ {n} a_ {i, sigma (i)}}$ kde ${ displaystyle {H_ {n}}}$ je sada n-permutací, které mají pouze jeden cyklus):${ displaystyle operatorname {ham} (A) = Sigma _ {J subseteq {2, dots, n }} det (A_ {J}) operatorname {per} (A _ { bar {J }}) (- 1) ^ {| J |}}$ . v charakteristický 2 druhá rovnost se změní na ${ displaystyle operatorname {ham} (A) = Sigma _ {J subseteq {2, dots, n }} det (A_ {J}) operatorname {det} (A _ { bar {J }})}$ co tedy poskytuje příležitost k výpočtu polynomiálního času Hamiltonovský cyklus polynom libovolného unitární ${ displaystyle U}$ (tj. takové, že ${ displaystyle U ^ {T} U = I}$ kde ${ displaystyle I}$ je identita nxn-matrix), protože každá menší z takové matice se shoduje s jejím algebraickým doplňkem: ${ displaystyle operatorname {ham} (U) = operatorname {det} ^ {2} (U + I _ {/ 1})}$ kde ${ displaystyle I _ {/ 1}}$ je identita nxn-matice se vstupem indexů 1,1 nahrazených 0. Navíc ji lze zase dále zobecnit pro unitární nxn-matice ${ displaystyle U}$ tak jako ${ displaystyle operatorname {ham_ {K}} (U) = operatorname {det} ^ {2} (U + I _ {/ K})}$ kde ${ displaystyle K}$ je podmnožinou {1, ..., n}, ${ displaystyle I _ {/ K}}$ je identita nxn-matice s položkami indexů k, k nahrazených 0 pro všechna k patřící k ${ displaystyle K}$a definujeme ${ displaystyle operatorname {ham_ {K}} (A) = součet _ { sigma v H_ {n} {(K)}} prod _ {i = 1} ^ {n} a_ {i, sigma (i)}}$ kde ${ displaystyle {H_ {n} {(K)}}}$ je sada n-permutací, jejichž každý cyklus obsahuje alespoň jeden prvek ${ displaystyle K}$.)

Tento vzorec implikuje následující identity nad poli charakteristický 3:

pro všechny invertibilní ${ displaystyle A}$

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

pro všechny unitární ${ displaystyle U}$ , tj. čtvercová matice ${ displaystyle U}$ takhle ${ displaystyle U ^ {T} U = I ,}$ kde ${ displaystyle I}$ je matice identity odpovídající velikosti,

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

kde ${ displaystyle V}$ je matice, jejíž položky jsou kostkami odpovídajících položek ${ displaystyle U}$.

Bylo také ukázáno (Kogan (1996) ), že pokud definujeme čtvercovou matici ${ displaystyle A}$ jako k-semi-unitární, když ${ displaystyle pozice (A ^ {T} A-I ,)}$ = k, permanent 1-semi-unitární matice je vypočítatelný v polynomiálním čase přes pole charakteristický 3, zatímco pro k > 1 problém se stává # 3-P-kompletní. (Paralelní teorie se týká Hamiltonovský cyklus polynom v charakteristický 2: zatímco jeho výpočet na jednotných maticích je proveditelný v polynomiálním čase, problém je # 2-P-úplný pro k-polojednotkové pro libovolné k> 0). Druhý výsledek byl v roce 2017 v zásadě prodloužen (Knezevic & Cohen (2017) ) a bylo prokázáno, že v charakteristický 3 existuje jednoduchý vzorec týkající se stálic čtvercové matice a její částečné inverze (pro ${ displaystyle A_ {11}}$ a ${ displaystyle A_ {22}}$ být čtvercový, ${ displaystyle A_ {11}}$ bytost invertibilní ):

${ 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)}$

a umožňuje polynomiálně-časově omezit výpočet permanentu matice nxn s podmnožinou řádků k nebo k-1 vyjádřitelných jako lineární kombinace jiné (disjunktní) podmnožiny řádků k na výpočet stálice ( nk) x (nk) - nebo (n-k + 1) x (n-k + 1) -matice odpovídajícím způsobem, a proto zavedl operátor komprese (analogický s Gaussovou modifikací použitou pro výpočet determinantu), který „zachovává“ trvale v charakteristický 3. (Analogicky by stálo za zmínku, že Hamiltonovský cyklus polynom v charakteristický 2 má také své invariantní maticové komprese, s přihlédnutím ke skutečnosti, že ham (A) = 0 pro jakoukoli nxn-matici A, která má tři stejné řádky, nebo, pokud n> 2, pár indexů i, j takový, že jeho i -th a j-th řádky jsou identické a jeho i-tý a j-tý sloupec jsou také identické.) Uzavření tohoto operátoru je definováno jako limit jeho postupné aplikace spolu s transformací transformace (používá se pokaždé, když operátor opustí neporušená matice) je také mapování operátorů, když je aplikováno na třídy matic, jedna třída do druhé. Zatímco operátor komprese mapuje třídu 1-semi-unitárních matic do sebe a do tříd unitární a 2-semi-unitární, kompresní uzávěr 1-semi-unitární třídy (stejně jako třídy matic obdržených od unitární ty prostřednictvím nahrazení jednoho řádku libovolným řádkovým vektorem - permanent takové matice je prostřednictvím Laplaceovy expanze součtem permanentů 1-polojednotkových matic a podle toho vypočítatelný v polynomiálním čase) je dosud neznámý a napjatý související s obecným problémem výpočetní složitosti permanentu v charakteristický 3 a hlavní otázka P versus NP: jak bylo ukázáno v (Knezevic & Cohen (2017) ), pokud je takový kompresní uzávěr množinou všech čtvercových matic nad polem charakteristický 3 nebo alespoň obsahuje třídu matice, na které je výpočet stálého # 3-P-kompletní (jako třída 2-semi-unitárních matic), pak permanent je vypočítatelný v polynomiálním čase v tomto charakteristický.

Kromě toho je problém najít a klasifikovat všechny možné analogy kompresí s trvalou ochranou, které existují v charakteristický 3 pro další primární charakteristiky byl formulován (Knezevic & Cohen (2017) ), přičemž poskytuje následující identitu pro matici nxn ${ displaystyle A}$ a dva n-vektory (mající všechny své záznamy z množiny {0, ..., p-1}) ${ displaystyle alpha}$ a ${ displaystyle beta}$ takhle ${ displaystyle { sum _ {i = 1} ^ {n} alpha _ {i}} = { sum _ {j = 1} ^ {n} beta _ {j}}}$, platné v libovolném prime charakteristický p:

${ 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}}}$

kde pro matici nxm ${ displaystyle M}$, n-vektor ${ displaystyle x}$ a m-vektor ${ displaystyle y}$, oba vektory mají všechny své záznamy z množiny {0, ..., p-1}, ${ displaystyle M ^ {(x, y)}}$ označuje matici přijatou z ${ displaystyle M}$ opakováním ${ displaystyle x_ {i}}$ krát jeho i-tý řádek pro i = 1, ..., na a ${ displaystyle y_ {j}}$ krát jeho j-tý sloupec pro j = 1, ..., m (pokud je multiplicita některého řádku nebo sloupce rovna nule, znamenalo by to, že řádek nebo sloupec byl odstraněn, a proto je tento pojem zobecněním pojmu submatice), a ${ displaystyle { vec {1}} _ {n}}$ označuje n-vektor, jehož položky se rovnají jednotě. Tato identita je přesným analogem klasického vzorce, který vyjadřuje moll matice skrze moll její inverze, a proto ukazuje (ještě jednou) jakousi dualitu mezi determinantem a permanentem jako relativní imananty. (Vlastně jeho vlastní analogie pro hafnian symetrie ${ displaystyle A}$ a liché prvočíslo p je ${ 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 + součet _ {i = 1} ^ {n} alpha _ {i}}}$ ).

A jako ještě širší zobecnění pro částečný inverzní případ v prime charakteristický p, pro ${ displaystyle A_ {11}}$, ${ displaystyle A_ {22}}$ být čtvercový, ${ displaystyle A_ {11}}$ bytost invertibilní a velikosti ${ displaystyle {n_ {1}}}$X${ displaystyle {n_ {1}}}$, a ${ displaystyle { sum _ {i = 1} ^ {n} alpha _ {i}} = { sum _ {j = 1} ^ {n} beta _ {j}}}$, je zde také identita

${ 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 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}}}$

kde společné vektory multiplicity řádků / sloupců ${ displaystyle alpha}$ a ${ displaystyle beta}$ pro matici ${ displaystyle A}$ generovat odpovídající vektory multiplicity řádků / sloupců ${ displaystyle alpha _ {s}}$ a ${ displaystyle beta _ {t}}$, s, t = 1,2, pro své bloky (stejné obavy ${ displaystyle A}$je částečná inverze na pravé straně rovnosti).

Přibližný výpočet

Když se položky z A jsou nezáporné, permanent lze vypočítat přibližně v pravděpodobnostní polynomiální čas, až do chyby εM, kde M je hodnota permanentu a ε> 0 je libovolné. Jinými slovy, existuje a plně randomizované aproximační schéma v polynomiálním čase (FPRAS) (Jerrum, Vigoda a Sinclair (2001) chyba harvtxt: žádný cíl: CITEREFJerrumVigodaSinclair2001 (Pomoc)).

Nejobtížnějším krokem ve výpočtu je konstrukce algoritmu vzorek téměř jednotně ze sady všech dokonalých shody v daném bipartitním grafu: jinými slovy plně polynomický téměř uniformní vzorkovač (FPAUS). To lze provést pomocí a Markovský řetězec Monte Carlo algoritmus, který používá a Vláda metropole definovat a spustit Markovův řetězec jehož distribuce je téměř stejná a jehož doba míchání je polynom.

Je možné přibližně spočítat počet perfektních shody v grafu pomocí samo-redukovatelnost permanentního, pomocí FPAUS v kombinaci se známým snížením ze vzorkování na počítání kvůli Jerrum, Valiant & Vazirani (1986) chyba harvtxt: žádný cíl: CITEREFJerrumValiantVazirani1986 (Pomoc). Nechat ${ displaystyle M (G)}$ označte počet perfektních shody v ${ displaystyle G}$. Zhruba pro každou konkrétní hranu ${ displaystyle e}$ v ${ displaystyle G}$vzorkováním mnoha shody v ${ displaystyle G}$ a počítat, kolik z nich odpovídá ${ displaystyle G setminus e}$, lze získat odhad poměru ${ displaystyle rho = { frac {M (G)} {M (G setminus e)}}}$. Číslo ${ displaystyle M (G)}$ je tedy ${ displaystyle rho M (G setminus e)}$, kde ${ displaystyle M (G setminus e)}$ lze aproximovat rekurzivně stejnou metodou.

Další třídou matic, pro kterou lze trvalou přibližně vypočítat, je sada kladně semidefinitní matice (složitost-teoretický problém aproximace permanentu takových matic v rámci multiplikativní chyby je považován za otevřený^[7]). Odpovídající randomizovaný algoritmus je založen na modelu vzorkování bosonu a používá k tomu vlastní nástroje kvantová optika, reprezentovat permanent kladně semidefinitních matic jako očekávanou hodnotu konkrétní náhodné proměnné. Ten je pak aproximován středním průměrem vzorku.^[8] Tento algoritmus pro určitou sadu pozitivně semidefinitních matic aproximuje jejich permanentní v polynomiálním čase až do aditivní chyby, která je spolehlivější než u klasického klasického polynomiálně-časového algoritmu od Gurvitsa.^[9]

Poznámky

Reference

Další čtení

• Barvinok, A. (2017), „Aproximace stálých a hafňanů“, Diskrétní analýza, arXiv:1601.07518, doi:10.19086 / da.1244.