Holografický algoritmus - Holographic algorithm

v počítačová věda, a holografický algoritmus je algoritmus, který používá holografickou redukci. Holografická redukce je konstantní čas snížení který mapuje fragmenty řešení mnoho na mnoho tak, že součet fragmentů řešení zůstává nezměněn. Tyto koncepty představil Leslie Valiant, který je zavolal holografické protože „jejich účinek lze chápat jako produkci interferenčních vzorů mezi fragmenty řešení“.^[1] Algoritmy nesouvisejí s laserem holografie, s výjimkou metaforicky. Jejich síla pochází ze vzájemného zrušení mnoha příspěvků na částku, analogickou s interferenčními vzory v hologramu.^[2]

K hledání byly použity holografické algoritmy polynomiální čas řešení problémů bez dříve známých řešení pro zvláštní případy uspokojivost, vrcholový kryt, a další problémy s grafy.^[3] Obdrželi pozoruhodné pokrytí kvůli spekulacím, že jsou pro EU relevantní Problém P versus NP^[2] a jejich dopad na teorie výpočetní složitosti. Ačkoli některé z obecných problémů jsou # P-tvrdé problémy, vyřešené speciální případy nejsou samy o sobě # P-hard, a proto neprokazují FP = #P.

Holografické algoritmy mají určité podobnosti kvantový výpočet, ale jsou zcela klasické.^[4]

Holantovy problémy

Holografické algoritmy existují v kontextu Holantových problémů, které zobecňují počítání problémy s uspokojením omezení (#CSP). Instance #CSP je hypergraf G=(PROTI,E) volal graf omezení. Každý hyperedge představuje proměnnou a každý vrchol ${displaystyle v}$ je přiřazeno omezení ${displaystyle f_ {v}.}$ Vrchol je připojen k hyperedge, pokud omezení na vrcholu zahrnuje proměnnou na hyperedge. Problémem počítání je výpočet

{displaystyle sum _ {sigma: E o {0,1}} prod _ {vin V} f_ {v} (sigma | _ {E (v)}), ~~~~~~~~~~~ (1) }

což je součet za všechna přiřazení proměnných, produkt každého omezení, kde vstupy do omezení ${displaystyle f_ {v}}$ jsou proměnné na dopadajících hyper-hranách ${displaystyle v}$ .

Holantův problém je jako #CSP, kromě toho, že vstup musí být graf, nikoli hypergraf. Omezení třídy vstupních grafů tímto způsobem je skutečně zobecněním. Vzhledem k instanci #CSP nahraďte každý hyperedge E velikosti s s vrcholem proti stupně s s hranami dopadajícími na vrcholy obsažené v E. Omezení je aktivní proti je funkce rovnosti arity s. To identifikuje všechny proměnné na hranách, ke kterým došlo proti, což je stejný účinek jako jediná proměnná na hyperedge E.

V kontextu Holantových problémů se výraz v (1) nazývá Holant po souvisejícím exponenciálním součtu zavedeném Valiantem.^[5]

Holografická redukce

Standardní technikou v teorii složitosti je a mnoho-jedna redukce, kde je instance jednoho problému redukována na instanci jiného (doufejme, že jednoduššího) problému. Holografické redukce mezi dvěma výpočetními problémy však zachovávají součet řešení, aniž by nutně zachovávaly korespondenci mezi řešeními.^[1] Například lze zachovat celkový počet řešení v obou sadách, i když jednotlivé problémy nemají odpovídající řešení. Součet lze také zvážit, namísto pouhého spočítání počtu řešení pomocí lineární základní vektory.^[3]

Obecný příklad

Je vhodné uvažovat o holografických redukcích na bipartitních grafech. Obecný graf lze vždy transformovat do bipartitního grafu při zachování hodnoty Holant. To se provádí nahrazením každé hrany v grafu cestou délky 2, která je také známá jako 2-úsek grafu. Aby byla zachována stejná Holantova hodnota, je každému novému vrcholu přiřazeno omezení binární rovnosti.

Zvažte bipartitní graf G=(U,PROTI,E) kde omezení přiřazené každému vrcholu ${displaystyle uin U}$ je ${displaystyle f_ {u}}$ a omezení přiřazené každému vrcholu ${displaystyle vin V}$ je ${displaystyle f_ {v}}$ . Označte tento problém počítání pomocí ${displaystyle {ext {Holant}} (G, f_ {u}, f_ {v}).}$ Pokud vrcholy v U jsou považovány za jeden velký vrchol stupně |E|, pak omezení tohoto vrcholu je tenzorový produkt z ${displaystyle f_ {u}}$ sama se sebou |U| krát, což je označeno ${displaystyle f_ {u} ^ {další časy | U |}.}$ Stejně tak, pokud vrcholy v PROTI jsou považovány za jeden velký vrchol stupně |E|, pak omezení tohoto vrcholu je ${displaystyle f_ {v} ^ {další časy | V |}.}$ Nechte omezení ${displaystyle f_ {u}}$ být vyjádřena jeho váženou hodnotou pravdivostní tabulka jako vektor řádku a omezení ${displaystyle f_ {v}}$ být reprezentován jeho váženou pravdivostní tabulkou jako vektor sloupce. Pak je Holant tohoto grafu omezení jednoduše ${displaystyle f_ {u} ^ {otimes | U |} f_ {v} ^ {otimes | V |}.}$

Nyní pro jakýkoli komplex 2: 2 invertibilní matice T (sloupce, které jsou lineárními bázovými vektory zmíněnými výše), je mezi nimi holografická redukce ${displaystyle {ext {Holant}} (G, f_ {u}, f_ {v})}$ a ${displaystyle {ext {Holant}} (G, f_ {u} T ^ {otimes (deg u)}, (T ^ {- 1}) ^ {otimes (deg v)} f_ {v}).}$ Chcete-li to vidět, vložte matici identity ${displaystyle T ^ {otimes | E |} (T ^ {- 1}) ^ {otimes | E |}}$ mezi ${displaystyle f_ {u} ^ {otimes | U |} f_ {v} ^ {otimes | V |}}$ dostat

{displaystyle f_ {u} ^ {otimes | U |} f_ {v} ^ {otimes | V |}}

{displaystyle = f_ {u} ^ {otimes | U |} T ^ {otimes | E |} (T ^ {- 1}) ^ {otimes | E |} f_ {v} ^ {otimes | V |}}

{displaystyle = left (f_ {u} T ^ {otimes (deg u)} ight) ^ {otimes | U |} left (f_ {v} (T ^ {- 1}) ^ {otimes (deg v)} ight ) ^ {další časy | V |}.}

Tím pádem, ${displaystyle {ext {Holant}} (G, f_ {u}, f_ {v})}$ a ${displaystyle {ext {Holant}} (G, f_ {u} T ^ {otimes (deg u)}, (T ^ {- 1}) ^ {otimes (deg v)} f_ {v})}$ mít přesně stejnou Holantovu hodnotu pro každý graf omezení. V podstatě definují stejný problém počítání.

Konkrétní příklady

Vrcholové kryty a nezávislé sady

Nechat G být graf. Mezi. Existuje korespondence 1: 1 vrcholové kryty z G a nezávislé sady z G. Pro jakoukoli sadu S vrcholů G, S je vrcholový kryt v G jen a jen pokud doplněk z S je nezávislý soubor v G. Počet vrcholů tedy pokrývá G je přesně stejný jako počet nezávislých sad G.

Rovnocennost těchto dvou problémů s počítáním lze prokázat také pomocí holografické redukce. Pro jednoduchost, pojďme G být 3-běžný graf. 2-úsek G dává bipartitní graf H=(U,PROTI,E), kde U odpovídá hranám v G a PROTI odpovídá vrcholům v G. Holantův problém, který přirozeně odpovídá počítání počtu vrcholů v G je ${displaystyle {ext {Holant}} (H, {ext {OR}} _ {2}, {ext {EQUAL}} _ {3}).}$ Pravdivostní tabulka OR₂ jako vektor řádku je (0,1,1,1). Pravdivá tabulka EQUAL₃ jako vektor sloupce je ${displaystyle (1,0,0,0,0,0,0,1) ^ {T} = {egin {bmatrix} 1 0end {bmatrix}} ^ {další 3} + {egin {bmatrix} 0 1end {bmatrix}} ^ {další 3}}$ . Pak pod holografickou transformací ${displaystyle {egin {bmatrix} 0 & 1 1 & 0end {bmatrix}},}$

{displaystyle {ext {OR}} _ {2} ^ {otimes | U |} {ext {EQUAL}} _ {3} ^ {otimes | V |}}

{displaystyle = (0,1,1,1) ^ {otimes | U |} vlevo ({egin {bmatrix} 1 0end {bmatrix}} ^ {otimes 3} + {egin {bmatrix} 0 1end {bmatrix} } ^ {otimes 3} ight) ^ {otimes | V |}}

{displaystyle = (0,1,1,1) ^ {otimes | U |} {egin {bmatrix} 0 & 1 1 & 0end {bmatrix}} ^ {otimes | E |} {egin {bmatrix} 0 & 1 1 & 0end {bmatrix}} ^ {otimes | E |} vlevo ({egin {bmatrix} 1 0end {bmatrix}} ^ {otimes 3} + {egin {bmatrix} 0 1end {bmatrix}} ^ {otimes 3} ight) ^ {otimes | V |}}

{displaystyle = left ((0,1,1,1) {egin {bmatrix} 0 & 1 1 & 0end {bmatrix}} ^ {otimes 2} ight) ^ {otimes | U |} left (left ({egin {bmatrix} 0 & 1 1 & 0end {bmatrix}} {egin {bmatrix} 1 0end {bmatrix}} ight) ^ {otimes 3} + left ({egin {bmatrix} 0 & 1 1 & 0end {bmatrix}} {egin {bmatrix} 0 1end {bmatrix }} ight) ^ {otimes 3} ight) ^ {otimes | V |}}

{displaystyle = (1,1,1,0) ^ {otimes | U |} vlevo ({egin {bmatrix} 0 1end {bmatrix}} ^ {otimes 3} + {egin {bmatrix} 1 0end {bmatrix} } ^ {otimes 3} ight) ^ {otimes | V |}}

{displaystyle = {ext {NAND}} _ {2} ^ {otimes | U |} {ext {EQUAL}} _ {3} ^ {otimes | V |},}

který je ${displaystyle {ext {Holant}} (H, {ext {NAND}} _ {2}, {ext {EQUAL}} _ {3}),}$ Holantův problém, který přirozeně odpovídá počítání počtu nezávislých sad G.

Dějiny

Stejně jako u jakéhokoli typu redukce ani holografická redukce sama o sobě nepřináší polynomiální časový algoritmus. Aby bylo možné získat algoritmus polynomiálního času, musí být problém redukovaný na také mít algoritmus polynomiálního času. Původní aplikace holografických algoritmů společnosti Valiant použila holografickou redukci na problém, kde je každé omezení realizovatelné matchgates,^[1] který právě prokázal, je přijatelný dalším snížením počtu perfektní shody v rovinný graf.^[6] Druhý problém je možné vyřešit pomocí Algoritmus FKT, který se datuje do šedesátých let.

Brzy poté Valiant našel holografické algoritmy s redukcemi na matchgates pro #₇ Pl -Rtw-Pondělí -3CNF a #₇Pl-3/2Bip -VC.^[7] Tyto problémy se mohou zdát poněkud nepřirozené, zejména s ohledem na modul. O obou problémech bylo již známo, že jsou # P-tvrdé při ignorování modulu a Valiant dodal důkazy # P-tvrdosti modulo 2, které také používaly holografické redukce. Valiant našel tyto dva problémy pomocí počítačového vyhledávání, které hledalo problémy s holografickými redukcemi na matchgates. Zavolal jejich algoritmy náhodné algoritmyříká: „Při aplikaci termínu náhodný na algoritmus hodláme poukázat na to, že algoritmus vzniká uspokojením zjevně obtížné množiny omezení.“ „Obtížnou“ sadou omezení jsou polynomiální rovnice, které, pokud jsou splněny, znamenají existenci holografické redukce, která by odpovídala realizovatelným omezením.

Po několika letech vývoje (tzv.) Teorie podpisů matchgate byli Jin-Yi Cai a Pinyan Lu schopni vysvětlit existenci dvou náhodných algoritmů Valiant.^[3] Tyto dva problémy jsou jen speciální případy dvou mnohem větších rodin problémů: #_2^k-1Pl-Rtw-Mon-kCNF a #_2^k-1Pl-k / 2Bip-VC pro jakékoli kladné celé číslo k. Modul 7 je jen třetí Mersenne číslo a Cai a Lu ukázali, že tyto typy problémů s parametry k lze vyřešit v polynomiálním čase přesně, když je modul kčíslo Mersenne pomocí holografických redukcí k matchgates a Čínská věta o zbytku.

Přibližně ve stejnou dobu dali Jin-Yi Cai, Pinyan Lu a Mingji Xia první holografický algoritmus, který se nesnížil na problém, který lze vyřešit pomocí matchgates.^[5] Místo toho se snížili na problém, který lze vyřešit pomocí Fibonacciho bran, které jsou symetrický omezení, jejichž pravdivostní tabulky splňují a relace opakování podobný tomu, který definuje Fibonacciho čísla. Také použili holografické redukce k prokázání, že určité problémy s počítáním jsou # P-tvrdé. Od té doby se holografické redukce značně používají jako přísady jak v polynomiálních časových algoritmech, tak v důkazech tvrdosti # P.

Reference

^ ^A ^b ^C Statečný, Leslie (17. – 19. Října 2004). Holografické algoritmy (rozšířený abstrakt). FOCS 2004. Řím, Itálie: IEEE Computer Society. 306–315. doi:10.1109 / FOCS.2004.34. ISBN 0-7695-2228-9.
^ ^A ^b Hayes, Brian (Leden – únor 2008). „Náhodné algoritmy“. Americký vědec.
^ ^A ^b ^C Cai, Jin-Yi; Lu, Pinyan (2011). "Holografické algoritmy: Od umění k vědě". J. Comput. Syst. Sci. 77 (1): 41–61. doi:10.1016 / j.jcss.2010.06.005.
^ Cai, Jin-Yi (červen 2008). Msgstr "Holografické algoritmy: sloupec pro hosty". Novinky SIGACT. New York, NY, USA: ACM. 39 (2): 51–81. doi:10.1145/1388240.1388254. ISSN 0163-5700.
^ ^A ^b Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji (2008). Holografické algoritmy Fibonacciho Gatesa a holografické redukce pro tvrdost. FOCS. IEEE Computer Society. 644–653. doi:10.1109 / FOCS.2008.34. ISBN 978-0-7695-3436-7.
^ Statečný, Leslie (2002). "Kvantové obvody, které lze klasicky simulovat v polynomiálním čase". SIAM Journal on Computing. 31 (4): 1229–1254. doi:10.1137 / S0097539700377025.
^ Leslie G. Valiant (2006). Náhodné Algorthims [Náhodné algoritmy]. Základy informatiky, IEEE Annual Symposium on. IEEE Computer Society. 509–517. doi:10.1109 / FOCS.2006.7. ISBN 0-7695-2720-5.

[valiant-1] A ^b ^C Statečný, Leslie (17. – 19. Října 2004). Holografické algoritmy (rozšířený abstrakt). FOCS 2004. Řím, Itálie: IEEE Computer Society. 306–315. doi:10.1109 / FOCS.2004.34. ISBN 0-7695-2228-9.

[americanscientist-2] A ^b Hayes, Brian (Leden – únor 2008). „Náhodné algoritmy“. Americký vědec.

[art-3] A ^b ^C Cai, Jin-Yi; Lu, Pinyan (2011). "Holografické algoritmy: Od umění k vědě". J. Comput. Syst. Sci. 77 (1): 41–61. doi:10.1016 / j.jcss.2010.06.005.

[survey-4] Cai, Jin-Yi (červen 2008). Msgstr "Holografické algoritmy: sloupec pro hosty". Novinky SIGACT. New York, NY, USA: ACM. 39 (2): 51–81. doi:10.1145/1388240.1388254. ISSN 0163-5700.

[fibonacci-5] A ^b Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji (2008). Holografické algoritmy Fibonacciho Gatesa a holografické redukce pro tvrdost. FOCS. IEEE Computer Society. 644–653. doi:10.1109 / FOCS.2008.34. ISBN 978-0-7695-3436-7.

[6] Statečný, Leslie (2002). "Kvantové obvody, které lze klasicky simulovat v polynomiálním čase". SIAM Journal on Computing. 31 (4): 1229–1254. doi:10.1137 / S0097539700377025.

[7] Leslie G. Valiant (2006). Náhodné Algorthims [Náhodné algoritmy]. Základy informatiky, IEEE Annual Symposium on. IEEE Computer Society. 509–517. doi:10.1109 / FOCS.2006.7. ISBN 0-7695-2720-5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]