ISSN 1673-9418 CODEN JKYTA8E-mail: fcst @vipJournal of Frontiers of Computer Science and Technologyhttp://www.673-9418/2011/05(02)-012819Tel:+86-105lDO:103778 j.issn.1673-9418.2011.02.003全息算法的原理及應(yīng)用許道云貴州大學(xué)計(jì)算機(jī)科學(xué)系,貴陽(yáng)550025Principles and applications of Holographic algorithmXU DaoyunDepartment of Computer Science, Guizhou University, Guiyang 550025, ChinaCorrespondingauthor:E-mail:dyxu@gzu.edu.cnXU Daoyun. Principles and applications of holographic algorithm. Journal of Frontiers of Computer Scienceand Technology, 2011, 5(2): 128-146.Abstract: The analysis of basic theory, principle and application method about holographic algorithm is presentedfor reading and applying easily the algorithm. Examples, such as the counting problem for planar 3-CNF formulaswill help readers to understand some basic principles and applications. The relevant principle and method are helpfulto solve some counting problems in combination problems.Key words: holographic algorithm; reduction; counting problem摘要:分析了全息算法的基本理論、原理和使用方法,旨在簡(jiǎn)化對(duì)全息算法的理解并加以應(yīng)用;給出了幾個(gè)實(shí)例(如平面3CNF公式的計(jì)數(shù)問(wèn)題,以幫助讀者理解全息算法中的一些基本原理和方法。相關(guān)的原理和方法對(duì)解決某些組合計(jì)數(shù)問(wèn)題有所幫助關(guān)鍵詞:全息算法;歸約;計(jì)數(shù)問(wèn)題文獻(xiàn)標(biāo)識(shí)碼:A中圖分類號(hào):TP3011引言(簡(jiǎn)稱A-問(wèn)題)。即,對(duì)于給定的實(shí)例x,判定“x∈A”給定一個(gè)非空集合A,可以定義一個(gè)判定問(wèn)題是否為真?傳統(tǒng)的多項(xiàng)式時(shí)間歸約(A≤PB)是指*The National Natural Science Foundation of China under grant Noment Foundation of Guizhou Province of china(貴州省省長(zhǎng)基金)cYH中國(guó)煤化工學(xué)基金 the gCNMHGReceived 2010-02, Accepted 2010-06許道云:全息算法的原理及應(yīng)用129判定A問(wèn)題在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)換到判定B問(wèn)題,按此“向下歸約”的原理,如果能找到一個(gè)種從而將A-問(wèn)題解的存在性判定轉(zhuǎn)換成B問(wèn)題解的子(計(jì)數(shù))問(wèn)題B有多項(xiàng)式時(shí)間算法,則借助于全息存在性判定。形式上,存在一個(gè)多項(xiàng)式時(shí)間可計(jì)算函歸約關(guān)系,可以構(gòu)建計(jì)數(shù)問(wèn)題A的多項(xiàng)式時(shí)間算數(shù)f:A→B,使得:對(duì)任意的x,x∈Af(x)∈B。法。由此產(chǎn)生的算法稱為問(wèn)題A的全息算法在這一轉(zhuǎn)換過(guò)程中,A問(wèn)題解的一個(gè)分支轉(zhuǎn)換成全息算法的有效性基于如下結(jié)論:尋找平面圖B-問(wèn)題解的一個(gè)分支。如果A≤pB,且A問(wèn)題是的完美匹配數(shù)可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算。具體來(lái)說(shuō),NP完全的,則B問(wèn)題是NP難的。從20世紀(jì)70一個(gè)平面圖的完美匹配數(shù)可以轉(zhuǎn)化成計(jì)算一個(gè)矩年代Cook證明SAT問(wèn)題是NP完全問(wèn)題以后,以陣行列式值的平方根5。SAT問(wèn)題為種子,按上述“向上歸約”的原理,只于是,全息算法的種子算法是:平面圖的完美要構(gòu)建一個(gè)多項(xiàng)式歸約,且證明B-問(wèn)題在NP類中,匹配數(shù)的多項(xiàng)式時(shí)間算法。就可以證明B問(wèn)題是NP完全的。用這樣的方法證全息算法的引入,解決了大量從前沒(méi)有多項(xiàng)式明了圖論中的許多問(wèn)題(如:哈密爾頓問(wèn)題、結(jié)點(diǎn)覆算法的計(jì)數(shù)問(wèn)題,使許多原來(lái)認(rèn)為很難的計(jì)數(shù)問(wèn)題蓋問(wèn)題等)及其他許多組合問(wèn)題都是NP完全問(wèn)題。有了多項(xiàng)式求解算法26直觀上,NP完全問(wèn)題是當(dāng)前計(jì)算能力不可承受的,根據(jù)“向下歸約”原理,全息算法主要用于驗(yàn)NP難問(wèn)題表現(xiàn)在指數(shù)時(shí)間以上的算法求解。這似證 Valiant計(jì)數(shù)問(wèn)題有多項(xiàng)式求解算法,其主要思想乎沒(méi)有對(duì)實(shí)際應(yīng)用帶來(lái)有用的結(jié)果和提供解決問(wèn)是將計(jì)數(shù)問(wèn)題轉(zhuǎn)換為一個(gè)平面圖的完美匹配多項(xiàng)題的有效方法,僅證明該問(wèn)題難解。實(shí)際工作和應(yīng)式計(jì)算問(wèn)題。由于一個(gè)平面圖的完美匹配多項(xiàng)式計(jì)用中,往往利用近似算法、隨機(jī)算法等方法求近似算問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)求解,從而原計(jì)數(shù)問(wèn)題解。 Valiant在2004年提出的全息歸約及算法holo在多項(xiàng)式時(shí)間內(nèi)可解。完成這一轉(zhuǎn)換過(guò)程稱為全息graphic reduction and algorithms),在計(jì)算復(fù)雜性領(lǐng)歸約。在轉(zhuǎn)換過(guò)程中,本質(zhì)上要構(gòu)造一個(gè)平面圖作域內(nèi),解決了許多驚人的結(jié)果:許多原來(lái)認(rèn)為只有為基圖,并構(gòu)造一個(gè)2階(或更高階)的可逆矩陣作指數(shù)時(shí)間算法的問(wèn)題,用全息算法建立了多項(xiàng)式算為基矩陣,利用基矩陣對(duì)各種基本狀態(tài)進(jìn)行長(zhǎng)編碼,法1-2。利用張積表示所有可能組合,構(gòu)造恰當(dāng)?shù)漠a(chǎn)生器和全息歸約是近年來(lái)計(jì)算復(fù)雜性研究領(lǐng)域中出現(xiàn)識(shí)別器,用產(chǎn)生器和識(shí)別器取代基圖中的結(jié)點(diǎn)(或的一種全新的歸約方法,全息歸約是計(jì)數(shù)問(wèn)題之間邊),并指定或引入一組邊作為中間件連接產(chǎn)生器的歸約,借助歸約變換,將另一個(gè)問(wèn)題的多項(xiàng)式求的輸出端和識(shí)別器的輸入端,從而形成一個(gè)平面匹解算法轉(zhuǎn)換到目標(biāo)問(wèn)題的多項(xiàng)式算法。配網(wǎng)格。通過(guò)中間件的狀態(tài)組合取值計(jì)算匹配網(wǎng)格般,解分支之間可能有四種關(guān)系:一對(duì)的 Holant量,而這個(gè)量剛好是匹配網(wǎng)格作為帶權(quán)圖對(duì)多、多對(duì)一、多對(duì)多。 valiant給出的全息歸約,的完美匹配多項(xiàng)式其特點(diǎn)是:將一個(gè)問(wèn)題的解分支的總和數(shù)對(duì)應(yīng)到另全息算法是計(jì)算復(fù)雜性領(lǐng)域內(nèi)一個(gè)全新的研究個(gè)問(wèn)題的解分支的總和數(shù)。即,考慮所有組合可對(duì)象。 Valiant提出全息算法以來(lái),多數(shù)研究工作是能下一個(gè)問(wèn)題的完整解的和數(shù)與另一個(gè)問(wèn)題的完在完善和簡(jiǎn)化該算法的理論和方法。理解全息算法整解的和數(shù)之間的關(guān)系。于是,不同問(wèn)題類的解分需要代數(shù)、組合數(shù)學(xué)、圖論、算法理論等方面的知支之間是多對(duì)多的關(guān)系。識(shí)。對(duì)一般人而言,理解、研究和應(yīng)用全息算法具問(wèn)題A到問(wèn)題B的一個(gè)全息歸約(A≤HB淇具有有一定的難度。為了簡(jiǎn)化和完善全息算法的思想特別意義:如果A≤B,且問(wèn)題B解的和數(shù)是多項(xiàng)蔡進(jìn)凵中國(guó)煤化工大量的工作:建立式可計(jì)算,則問(wèn)題A解的和數(shù)也是多項(xiàng)式可計(jì)算了全CNMHG數(shù)描述體系;基于的。即問(wèn)題A的解的和數(shù)有多項(xiàng)式算法Grassmann-Plucker等人的工作,建立了一般匹配門130Journal of Frontiers of Computer Science and Technology計(jì)算機(jī)科學(xué)與探索2011,5(2)的一個(gè)完備描述;給出了在保證完美匹配總數(shù)不變性布爾函數(shù)編碼問(wèn)題。對(duì)全息算法原理的詳細(xì)分析的前提下,通過(guò)引入輔助子圖處理原圖中的交叉旨在簡(jiǎn)化對(duì)全息算法的理解和應(yīng)用,對(duì)解決其他組邊,以建立圖的平面化的多項(xiàng)式時(shí)間算法;研究了合問(wèn)題提供幫助。涉及到的基本理論、方法和應(yīng)用不同基的關(guān)系與表示能力;提出了全息算法模板還可以參考文獻(xiàn)[15-19等10-15類比N完全問(wèn)題的證明方法,全息算法所走2基本概念和記號(hào)的路徑剛好相反:基于平面圖的完美匹配數(shù)計(jì)算在設(shè)G=(V,E,W)為一個(gè)邊帶權(quán)的無(wú)向圖,其中W多項(xiàng)式時(shí)間內(nèi)可解,只要證明所考慮的計(jì)數(shù)問(wèn)題能為G中邊集合E上的權(quán)函數(shù)。一般假定G中無(wú)自夠全息歸約到平面圖的完美匹配計(jì)數(shù)問(wèn)題,則可以回路(環(huán),即每一條邊e=(,j關(guān)聯(lián)(或稱飽和)的兩構(gòu)造出問(wèn)題的多項(xiàng)式時(shí)間算法。這在實(shí)際中是非常個(gè)結(jié)點(diǎn)i、j都不相同。一個(gè)邊子集EcE所關(guān)聯(lián)的有用的。結(jié)點(diǎn)集合記為mc(E)。一個(gè)邊子集EcE稱為G基于這樣的思路,全息算法的研究工作主要集的一個(gè)匹配,如果E中任意兩條不同的邊1、e2中在如下幾個(gè)方面:有l(wèi)mc(e1)∩lmc(2)=②,即不同邊無(wú)公共關(guān)聯(lián)結(jié)1)全息算法理論的逐步完善,并借助于其他點(diǎn)。一個(gè)匹配EsE是完美的,如果lm(E)=v方法、理論對(duì)算法的描述,使算法的構(gòu)建變得更容21圖的匹配多項(xiàng)式易和實(shí)用。(2)借助于全息算法,尋找某些計(jì)數(shù)問(wèn)題的多對(duì)于具有n個(gè)結(jié)點(diǎn)圖的G,引人變?cè)瘂x項(xiàng)式時(shí)間算法。1≤iabex-86c6c82③…⊙96c=進(jìn)一步分解成為:ae8.③c8c]8b18.8引理3設(shè)T=為一個(gè)基矩陣在全息算法中,給定二階基矩陣,利用張積生421 422(取行代碼:n=(a142),P=(a,22),對(duì)正整數(shù)成一個(gè)2階變換矩陣T。,T可以分解成子矩陣k1,k2…,k1≥1,C1,C2…,C1分別為長(zhǎng)度為2784,T。,,T。(其中k1十k2+…+k=k)聯(lián)系到量子算法中的基本思想:將一個(gè)兩矩陣U分解成若2,,2+的行向量,則有(行張積分解干二階西矩陣U1U2…,Un,而一個(gè)二階西矩陣U[C1C28.⑧C1。+++)對(duì)應(yīng)一個(gè)單比特量子門,由此分解構(gòu)造一個(gè)量子電Cr 8CT8k2 88C, 8路。全息算法中一個(gè)單值可用一個(gè)二維向量p/n)作考慮取“列代碼”情形,類似地,有基準(zhǔn)碼進(jìn)行編碼;量子算法中一個(gè)單值可用一個(gè)二引理4設(shè)T=n,]為一個(gè)基矩陣維向量(op>)進(jìn)行編碼。在此相似原理下,全息a22算法與量子算法具有相通之處1。取列代碼:n=41,p={2,對(duì)正整數(shù)k”4產(chǎn)生器與識(shí)別器k≥1,C,C2C分別為長(zhǎng)度為2,24,,24的在全息算法中,匹配門r(x的兩種特例產(chǎn)生列向量,則有(列張積分解)器與識(shí)別器)是最重要的基礎(chǔ)概念。T+)C18C288C1=(1)產(chǎn)生器:X=Q,Y≠②;T8kC187%C2.8T0C1(2)識(shí)別器:X≠⑧,Y=。借助于引理1、引理3與引理4,將用到如下結(jié)論:當(dāng)X=②,Y≠時(shí),廠xy退化為產(chǎn)生器記為設(shè)r={41a21(為一個(gè)基矩陣,其逆矩ry),如果Y上k,稱廠→為一個(gè)k輸出產(chǎn)生器(簡(jiǎn)中國(guó)煤化工(廠(xy)退化到一陣Tbi b=[n,p]。對(duì)兩組正整數(shù)k1,k2個(gè)長(zhǎng)HCNMHGu(r+p)為廠y的b2l by標(biāo)準(zhǔn)標(biāo)識(shí))。許道云:全息算法的原理及應(yīng)用135當(dāng)X≠②,Y=必時(shí),廠(xy)退化為識(shí)別器(記選擇適當(dāng)?shù)?×2基矩陣,由此基矩陣引入一種為廠x),如果X上=k,稱廠x→為一個(gè)k輸入識(shí)二維”行代碼n、p作為基準(zhǔn)碼類似于布爾變量別器(簡(jiǎn)稱k-識(shí)別器)標(biāo)準(zhǔn)標(biāo)識(shí)矩陣以(「(x)退化作為“一維”基準(zhǔn)碼).驗(yàn)證所有可能組合下,其計(jì)到一個(gè)長(zhǎng)度為2的列向量u(Ix→)(稱以(x)為數(shù)行向量由n、P的張積的線性疊加表示。Fx的標(biāo)準(zhǔn)標(biāo)識(shí))所研究的問(wèn)題是:u(F→y)作為函數(shù),如何在此產(chǎn)生器是在一個(gè)帶權(quán)圖G中指定一個(gè)結(jié)點(diǎn)子函數(shù)系”下展開(kāi)計(jì)算。如:當(dāng)Y上=3時(shí),有集Y作為其輸出端口,對(duì)Y的任一個(gè)子集Z,計(jì)算u(y)=個(gè)量 PerMmatch(G-2),所有不同子集情況下,得n⑧nnn nap到a(廠)。見(jiàn)圖2npdn(booo, bo01, bo1o, o11, 00, 601, 610 6)n⑧p⑧p●保留Pn⑧n0刪除Pn②pP⑧pnFig 2 Generator(Z=(2D)8p⑧圖2產(chǎn)生器(Z=(2)其中,b0,bon,bno,bn,b,bog,hn0,b1視為展開(kāi)以k=3為例:a(廠y)=(ao,0o0,o,o,10系數(shù)。系數(shù)用記號(hào):wG(y,x⑧y8z)表示,其a0,10,an),分量下標(biāo)是按01,2,3,4,5,6,7}中xz∈{m,p}。如:b01=G(T,p8n8p)。產(chǎn)的二進(jìn)制順序從左到右排序。下標(biāo)作為特征標(biāo),刪生器只考慮正迭加。即,展開(kāi)系數(shù)bbou,buo除的結(jié)點(diǎn)子集的對(duì)應(yīng)關(guān)系為bo1b0,hon,bo,hu只允許取0或1000001010011100101110111如:(2,0,0,2,0,2,2,0)=n⑧n⑧n+p⑧p⑧P,φ{(diào)3}(2}{2,3}{{{2{2,3其中n=(1,1),p=(1,-1)可見(jiàn),{1,2,3}的子集元素“從大到小”的字典序回憶一下CNF公式的主合取范式表示與“從左到右”的0/特征標(biāo)記一致。[0,1]=[n,p類似地,識(shí)別器也是在一個(gè)帶權(quán)圖G中指定01111111個(gè)結(jié)點(diǎn)子集X作為其輸入端口,對(duì)X的任一個(gè)子集10111111Z,計(jì)算一個(gè)量 PerfMatch(G-z),所有不同子集情110111111110況下,得到(廠x→)。見(jiàn)圖3。1011●保留11111101o刪除11110xvyvznvnvnFig 3 Recognizer(z=13, 4))圖3識(shí)別器(Z={3,4}Ivy-rv-yvz010Inv pvn以產(chǎn)生器的標(biāo)準(zhǔn)標(biāo)識(shí)a(Fy)為例,所研究的xy"yv氣問(wèn)題是:能否選擇一個(gè)2×2基矩陣,通過(guò)張積計(jì)算得到一個(gè)2*×2矩陣作為k編碼矩陣,一行代表一中國(guó)煤化工 pinp個(gè)函數(shù),k-編碼矩陣代表一個(gè)函數(shù)系(不一定正交)。CNMH GPVP要求u(廠→)能用該函數(shù)系線性疊加表示。y→ yv-] L111 LpvpJournal of Frontiers of Computer Science and technology計(jì)算機(jī)科學(xué)與探索2011,5(2)上述矩陣可作為0串的一種長(zhǎng)編碼方式(稱為00011「n’8n標(biāo)準(zhǔn)編碼)。逆矩陣,0011_m8p注意:[0,=[n,p是“一維”基準(zhǔn)碼,而全息0101|p8n算法中采用的是“二維”基準(zhǔn)碼。p'⑧p對(duì)于識(shí)別器,由基矩陣引入一種“二維”列代碼n、P作為基準(zhǔn)碼,類似考慮:(Tx→)的表示計(jì)可見(jiàn)4(10)0之間存套互算。如:當(dāng)|X上=3時(shí),有轉(zhuǎn)換關(guān)系。u(x→)=(n⑧n⑧n,nn⑧p,n⑧p⑧n,n②p⑧p,考慮向量(-1,0.0,1)的展開(kāi)表示:設(shè)(100=0402,其中Pn⑧n,p⑧n⑧p,p②p⑧n,p⑧p⑧p)pop600(bo0b1oh1)為待定常數(shù)。而on-1-11000110n⑧0-10001⑧系數(shù)用記號(hào):wR(fx→,xy②2)表示,其中-1000101P②P1000xy,z∈{n,p}。如:c101=wR(Fx→,P⑧n⑧p)。注意:此時(shí)x⑧y⑧z為列向量。通常,類似于mmmm所以,(4+101010h1)、(co,co0,con0,con,co,co,10,c1n)這樣的1111向量來(lái)自于原始計(jì)數(shù)問(wèn)題的計(jì)數(shù)(故稱為計(jì)數(shù)標(biāo)識(shí),(,1,0)。于是,(-1,0,0,D)=n⑧n+n8P+p8n。簡(jiǎn)稱標(biāo)識(shí))按定義,耿(Fy)、耿(x)是來(lái)自于帶權(quán)圖(產(chǎn)生器、識(shí)別器)的匹配計(jì)數(shù)表示向量(標(biāo)準(zhǔn)5計(jì)數(shù)問(wèn)題的形式化描述標(biāo)識(shí)本章討論一種計(jì)數(shù)問(wèn)題的形式化描述。一個(gè)自然的問(wèn)題是:對(duì)于同類的多個(gè)產(chǎn)生器X={x,…,x}為k個(gè)變量,其值域D的基數(shù)識(shí)別器,如何選擇一個(gè)基矩陣以此分別生成變換為d≥2。定義兩組布爾函數(shù):矩陣,要求滿足一定的約束關(guān)系下,將這些標(biāo)識(shí)與協(xié)調(diào)函數(shù):a:cX→{0,1}。簡(jiǎn)稱a-函數(shù)。標(biāo)準(zhǔn)標(biāo)識(shí)的互換關(guān)系聯(lián)系起來(lái)。傾4考惠A-(10()a(4,…飛)x={寫,寫…},=12…g。0,h2=,1=其中,x1,x2…,x,形成X的一個(gè)劃分。0/°a(,,…)取值用一個(gè)長(zhǎng)度為d的行向P量ax(X)表示。這里,n=[(-,1,(0,n,p]=[01,(1)有效函數(shù):B:cX→10,1。簡(jiǎn)稱β-函數(shù)。nX},閏,2,,r中國(guó)煤化工2編碼矩陣:其中penCNMHG另一個(gè)劃分。月(,…)取值用一個(gè)長(zhǎng)度為d"的列向量許道云:全息算法的原理及應(yīng)用137B(xj)表示。寫=c被解釋為:結(jié)點(diǎn)v通過(guò)邊v,")向相鄰注意:k+k2+…+k=m+m+…+m=k。結(jié)點(diǎn)v傳遞信息“v著c色”。定義一個(gè)叢函數(shù):(2)引人v=4個(gè)a-函數(shù)結(jié)點(diǎn)函數(shù)):a1(2,不3Mass(X)=[a(X1)@a2(X2)8.8ag(xg)4),a2(x1,x2),a3(x1,2,4)a4(x1,x3)。其中,A(X1)8B(X)Q8B(X)向量乘法)a1(2,與3,4)有時(shí)也記為:therwiseMass(X)=更換。a、圖9結(jié)點(diǎn)保留(刪除)與賦值對(duì)應(yīng)關(guān)系同為行向量(或列向量)。計(jì)算轉(zhuǎn)換以后,仍然沿用 Valiant的使用方法:兩類標(biāo)準(zhǔn)①a(x,)9=m(B(x)(產(chǎn)生器B的標(biāo)準(zhǔn)標(biāo)標(biāo)識(shí)的計(jì)算用同一個(gè)基、同類代碼識(shí),其中X1為B的輸出端口號(hào)集合8匹配網(wǎng)格的 Holant量②()月(x)=a(4,x)(識(shí)別器A的如果匹配網(wǎng)格圖是平面圖,則稱為平面匹配網(wǎng)標(biāo)準(zhǔn)標(biāo)識(shí),其中X為A,的輸入端口號(hào)集合)格。全息算法設(shè)計(jì)中,只考慮平面匹配網(wǎng)格,理由于是,原始計(jì)數(shù)來(lái)自于定理1。MassSum(a)=中國(guó)煤化工系到一個(gè)平面圖∑a1(x1)8a2(X2)98a2(X2GCNMHG識(shí)別器替代圖中XeNO. 1]E的結(jié)點(diǎn)或邊,再利用中間件關(guān)聯(lián),形成一個(gè)平面匹Journal of frontiers of Computer Science and Technology計(jì)算機(jī)科學(xué)與探索2011,5(2)配網(wǎng)格。將計(jì)數(shù)問(wèn)題轉(zhuǎn)換成平面匹配網(wǎng)格的匹配計(jì)對(duì)于連結(jié)邊{,e2…},一組編碼X∈{n,p數(shù)(或匹配質(zhì)量總和)問(wèn)題。對(duì)應(yīng)給{e,e2,e}一組編碼指派根據(jù)連結(jié)到產(chǎn)生直觀上,產(chǎn)生器是“發(fā)射”,識(shí)別器是“吸收”。器輸出端口和識(shí)別器輸入端口的聯(lián)系,將組產(chǎn)生器和一組識(shí)別器之間,通過(guò)中間件的連通x∈{n,p作如下兩種分解關(guān)系,計(jì)數(shù)問(wèn)題轉(zhuǎn)化為:在各種組合下,發(fā)射與組(1)按{,2…l連結(jié)到{B,B2,,B)的輸出合吸收之間的“有效”累計(jì)。端口的關(guān)系,通過(guò)適當(dāng)調(diào)整順序,將X分解為:81匹配網(wǎng)格X=X1⑧X2②X。其中,x1,X2,…,X分別為對(duì)于一個(gè)計(jì)數(shù)問(wèn)題4=(a(X1).a2(x2)…,x在B1B2B2輸出端口上的投影。a3(x2),x,(A(x1),2(X2)…月(X)),其中(2)按(,e2,,e}連結(jié)到{A,A,,A}的輸入1X1k(1≤長(zhǎng)≤gm(≤j≤),且端口的關(guān)系,通過(guò)適當(dāng)調(diào)整順序,將Ⅹ分解為∑k=∑X=X1⑧X2⑧.8Xr。其中,X1,X2,,Xr分別為X在{A1,A,…,A}輸人端口上的投影。如果存在一個(gè)2階基矩陣b=a142)_/n根據(jù)上述分解關(guān)系,對(duì)于指定的一組X的指派X∈{n,p},可以分別得到兩組o)量其逆矩陣b1=-(12=[m,p],使得如果條valG(B, X1), val (B2, X2),val(Be, X,)件成立(關(guān)于b=“的展開(kāi)系數(shù)1)在基矩陣b下,存在一組產(chǎn)生器B={B1,B2,…B},使得對(duì)每一個(gè)1≤i≤g,a(X)可以valR(A, X1), valR(A,, X2),,valR(A, X,)關(guān)于b1=[m,P1的展開(kāi)系數(shù))由B產(chǎn)生。即a(B1(X)=a(x。值得注意的是:如果waG(B1,X1)=1,則X出(2)在b1=b下,存在一組識(shí)別器A=A,現(xiàn)在產(chǎn)生器B的標(biāo)識(shí)向量的線性和中,否則,未出A24),使得對(duì)每一個(gè)1≤j≤r,BxX)可以現(xiàn)。如果wR(A,)=1,則對(duì)出現(xiàn)在識(shí)別器A由A識(shí)別。即a(4(x)=()月(X)的標(biāo)識(shí)向量的線性和中,否則,未出現(xiàn)。形式上,一個(gè)匹配網(wǎng)格由三個(gè)部分構(gòu)成:一組這就出現(xiàn)如下一致性檢測(cè)問(wèn)題:對(duì)于給定的產(chǎn)生器B={B,B2…B2}、一組識(shí)別器A={A,X∈{n,p({a,2,,}一組編碼指派,檢測(cè)下式A2…,A}、一組帶權(quán)為1的連結(jié)邊C={,e2…,}。是否成立匹配網(wǎng)格用=(A,B,C)表示?！浮莣G,x)「ⅡwRA,X)=182匹配網(wǎng)格的 Holant量1≤jr如果此局部檢測(cè)成功,說(shuō)明產(chǎn)生器與識(shí)別器關(guān)于對(duì)于給定的基b=(“,其逆b1=m,門1,設(shè)x∈(np一致否則,產(chǎn)生器與識(shí)別器在x下不P致在b下的匹配網(wǎng)格為定義一個(gè)量統(tǒng)計(jì)出所有的一致編碼指派。記為:g=(B,B2,…Bgl,e12…l,{A,42…A})Holant(2其中,連結(jié)邊{,e2…e}左端連結(jié)到{B1,B2,…,B}中國(guó)煤化工中的k個(gè)輸出端口,右端連結(jié)到(A,A2…,A}中的CNMH∏wR,X)k個(gè)輸入端口?！躩≤r許道云:全息算法的原理及應(yīng)用143通常記為:(4)對(duì)結(jié)點(diǎn)和邊的有效狀態(tài)(指派)s=(sy,sg)Holant(2)=可以定義一個(gè)質(zhì)量函數(shù)mas()∑「mw0(1.x)∏wK4.x任何在s=(sy,5g)下有效的結(jié)點(diǎn)(或邊),都會(huì)對(duì)mas(5)貢獻(xiàn)一個(gè)有效因子f(sv()(或表面上, Holan(2)的求和計(jì)算中含有指數(shù)f(sg(e))。一個(gè)有效狀態(tài)(指派)的質(zhì)量mas(s)被定項(xiàng)。然而,可將2理解為一個(gè)帶權(quán)有向圖G并將義為所有這些結(jié)點(diǎn)和邊所貢獻(xiàn)的因子的乘積。Holant(9)的計(jì)算問(wèn)題轉(zhuǎn)換為帶權(quán)有向圖G的完美(5)計(jì)數(shù)問(wèn)題則是對(duì)所有有效狀態(tài)(指派)的質(zhì)匹配總和 Perfmatch(G)的計(jì)算問(wèn)題。這樣,如果G量mg()求和。是平面圖,則由定理1, PerfMatch()可以在多項(xiàng)全息模板:對(duì)于一個(gè)給定的 valiant計(jì)數(shù)問(wèn)題,式時(shí)間內(nèi)完成。這就是全息算法的本質(zhì)和精髓。求解該問(wèn)題的全息模板具有如下結(jié)構(gòu):定理3對(duì)于給定的基b=[n,p],=(A,B,C)為在b下的匹配網(wǎng)格,G是Ω對(duì)應(yīng)的帶權(quán)圖,則有(1)構(gòu)造一個(gè)基b=-(這里假定取“二維”編Holant(2)= PerfMatch(G)碼,類似可以使用更高維的編碼)。推論1對(duì)于給定的基b=[v,p],如果』=(2)基圖G=(,E)(平面圖)中每一個(gè)結(jié)點(diǎn)(A,BC)是在b下的平面匹配網(wǎng)格,則Hoan)veV和邊e=(u,y)∈E分別作如下處理在多項(xiàng)式時(shí)間內(nèi)可計(jì)算。①結(jié)點(diǎn)替換:依據(jù)狀態(tài)集S,用一個(gè)產(chǎn)生器(或識(shí)別器)替換該結(jié)點(diǎn),產(chǎn)生器的端口數(shù)與結(jié)點(diǎn)度9全息模板數(shù)一致。為了形式化描述全息算法的基礎(chǔ)類型,蔡進(jìn)一②邊替換:依據(jù)狀態(tài)集Sg,用一個(gè)識(shí)別器(或等人給出了一種全息算法的形式化描述—一全息模產(chǎn)生器替換邊c=(n吵),識(shí)別器帶兩個(gè)輸入端口。板12-131一個(gè)連結(jié)的產(chǎn)生器的一個(gè)輸出端口,另一個(gè)連結(jié)vaan計(jì)數(shù)問(wèn)題:一↑wan計(jì)數(shù)問(wèn)題是帶有ν的產(chǎn)生器的一個(gè)輸出端口。如下結(jié)構(gòu)的計(jì)數(shù)問(wèn)題。(3)產(chǎn)生器和識(shí)別器的端口可適當(dāng)用外部結(jié)點(diǎn)(1)一個(gè)平面圖G=(,E)。表示。外部連結(jié)邊{=,,…,erl連結(jié)產(chǎn)生器引出的(2)兩個(gè)狀態(tài)集Sy、SE外部(端口)結(jié)點(diǎn)和識(shí)別器引出的外部端口)結(jié)點(diǎn)結(jié)點(diǎn)狀態(tài)集Sv:個(gè)指派X∈{n,p}對(duì)應(yīng)一個(gè)狀態(tài)s。如果廠為一個(gè)Sy:{sv:sv:v→D產(chǎn)生器,則walG(F,X)=f(s);如果廠為一個(gè)識(shí)別sv()為對(duì)結(jié)點(diǎn)ν有一個(gè)指派值;器,則walR(r,X)=f(s)。邊狀態(tài)集SE:(4)如果X∈{n,p}為一個(gè)無(wú)效指派,則對(duì)應(yīng)SE={E:SE:E→D2于X的 Holant量為0。sg(e)為對(duì)結(jié)點(diǎn)e有一個(gè)指派值。例如:3CNF公式匹配網(wǎng)格中,可用2產(chǎn)生器注:兩類指派域可能不一致替換變?cè)Y(jié)點(diǎn);用3-識(shí)別器替換子句結(jié)點(diǎn);連結(jié)邊(3)一個(gè)局部“接受”判定標(biāo)準(zhǔn)o:判定一個(gè)給則是公式的變?cè)泳鋱D中本身的邊。定的狀態(tài)指派s或sE下,局部的結(jié)點(diǎn)或邊是否“有效”(可接受)。對(duì)于一個(gè)k度結(jié)點(diǎn),形式上,一個(gè)局10部“接受”判定標(biāo)準(zhǔn)φ表現(xiàn)為一個(gè)映射:中國(guó)煤化工Φ:y×s→(0,1}(類似于CSP問(wèn)題中的約束)的計(jì)HCNMH生所有可能組合下土男仃H數(shù)問(wèn)題的計(jì)算轉(zhuǎn)換14 mal of Frontiers of Computer Science and Techno計(jì)算機(jī)科學(xué)與探索2012成一個(gè)平面匹配門的標(biāo)準(zhǔn)標(biāo)識(shí)矩陣計(jì)算問(wèn)題。如果102全息算法設(shè)計(jì)這樣的全息歸約關(guān)系存在,并可以在多項(xiàng)式時(shí)間內(nèi)(1)基的選擇完成,則原計(jì)數(shù)問(wèn)題在多項(xiàng)式時(shí)間內(nèi)可解。這是因?yàn)槠矫嫫ヅ溟T的標(biāo)準(zhǔn)標(biāo)識(shí)矩陣計(jì)算問(wèn)題在多項(xiàng)式取,n=(-11,p=(1,0)時(shí)間內(nèi)可解。(2)產(chǎn)生器匹配門設(shè)計(jì)全息歸約的目標(biāo)是:尋找集合對(duì)(X,Y)和一個(gè)考慮一個(gè)局部圖:G=(,E,W,V={12},E=基矩陣,并完成標(biāo)準(zhǔn)標(biāo)識(shí)矩陣以(T(xn)轉(zhuǎn)換計(jì)算過(guò)(a,2),wa,)=-1。程。求解計(jì)數(shù)問(wèn)題在所有可能組合下的計(jì)數(shù)表示。通過(guò)選擇適當(dāng)?shù)幕仃?將原始計(jì)數(shù)問(wèn)題在多項(xiàng)式1·12時(shí)間內(nèi)轉(zhuǎn)換成:一個(gè)集合對(duì)(X,)下平面匹配門Fig 10 Generator with a weighted edgerxn)的標(biāo)準(zhǔn)標(biāo)識(shí)矩陣(廠(x)的計(jì)算。而a(rxy)圖10一條帶權(quán)邊的產(chǎn)生器的計(jì)算可以在多項(xiàng)式時(shí)間內(nèi)完成,從而對(duì)于給定的產(chǎn)生器r的匹配門端口對(duì)(X,)的輸入、輸出計(jì)數(shù)問(wèn)題的所有可能計(jì)數(shù)表示能夠在多項(xiàng)式時(shí)間端口分別為:X=②,Y={,2}。內(nèi)完成。標(biāo)準(zhǔn)標(biāo)識(shí):u(=(-1,0,0,1),對(duì)應(yīng)的端口開(kāi)閉為使讀者能理解全息算法的使用,本節(jié)詳細(xì)給特征函數(shù)列:00,01,10,1)出一個(gè)計(jì)數(shù)問(wèn)題(# X-MATCHINGS)的全息算法的其中,1——一閉(刪除對(duì)應(yīng)結(jié)點(diǎn)),0—開(kāi)(保留對(duì)設(shè)計(jì)與分析應(yīng)結(jié)點(diǎn))10.1問(wèn)題描述引理5存在關(guān)于基b=,n=(-1),p=# X-MATCHINGS問(wèn)題輸入:一個(gè)平面帶權(quán)二部圖G=,EW),其00的產(chǎn)生器廠,使得中結(jié)點(diǎn)劃分為v=vUV2,邊權(quán)函數(shù)為w:E→Ru()=(-1,0.0,1)=n②n+n⑧p+p⑧n從而,walG(F,n⑧n)=ali(r,n⑧p)=walG(r,p且(v∈w)deg(v)=2]。n)=1,wlG(F,p⑧p)=0。輸出:∑masM)(求和取遍所有匹配(不一(3)識(shí)別器匹配門設(shè)計(jì)定是完美匹配)考慮一個(gè)局部圖(圖11)其中,mas(M)為匹配M的質(zhì)量,定義為如下兩項(xiàng)之積(1)正W(e)匹配權(quán)重(-1)∑W(e)其中, unsafe(M)為M的未飽和結(jié)點(diǎn)集,mc()為關(guān)聯(lián)結(jié)點(diǎn)v的邊集合。例如,在G=V,EW)中,假定每條邊上權(quán)重Fig.1 Recognizer for weighted edges joining to a node為1,v2中每個(gè)結(jié)點(diǎn)的度數(shù)為4,則# MATCHINGS圖11識(shí)別一個(gè)結(jié)點(diǎn)關(guān)聯(lián)的帶權(quán)邊的識(shí)別器輸出G=(v,EW)的匹配數(shù),但每個(gè)匹配被賦予形中國(guó)煤化工1,w2…,叫∈F,存如(-4)的權(quán)重,其中k為該匹配未飽和V2中的結(jié)在關(guān)CNMHG點(diǎn)數(shù)44,F-(1,0)的識(shí)別器廠,許道云:全息算法的原理及應(yīng)用145使得對(duì)所有的輸入x=x⑧x2⑧,8x∈tnp,其1l結(jié)束語(yǔ)系數(shù)值wR(廠,x)具有如下性質(zhì):全息算法主要用于驗(yàn)證 Valiant計(jì)數(shù)問(wèn)題有多valR(廠,x)=項(xiàng)式求解算法,其主要思想是將計(jì)數(shù)問(wèn)題轉(zhuǎn)換為一(+w2+…+w)個(gè)平面圖的完美匹配多項(xiàng)式計(jì)算問(wèn)題。由于一個(gè)平耳=P,V≠Dx=川面圖的完美匹配多項(xiàng)式計(jì)算問(wèn)題可以在多項(xiàng)式時(shí)otherwise間內(nèi)求解,從而原計(jì)數(shù)問(wèn)題在多項(xiàng)式時(shí)間內(nèi)可解(4)全息歸約構(gòu)造完成這一轉(zhuǎn)換過(guò)程稱為全息歸約。在轉(zhuǎn)換過(guò)程中對(duì)于平面帶權(quán)二部圖G=(V,E,W),其中結(jié)點(diǎn)本質(zhì)上要構(gòu)造一個(gè)平面圖作為基圖,并構(gòu)造一個(gè)2劃分為V=VUV2,邊權(quán)函數(shù)為W:E→R,階(或更高階)的可逆矩陣作為基矩陣,利用基矩陣vv∈V)deg(v)=2]。對(duì)各種基本狀態(tài)進(jìn)行長(zhǎng)編碼,利用張積表示所有可構(gòu)造如下平面匹配網(wǎng)格=(A,B,C):能組合,構(gòu)造恰當(dāng)?shù)漠a(chǎn)生器和識(shí)別器,用產(chǎn)生器和①v中的每個(gè)結(jié)點(diǎn)v,用引理5中的一個(gè)產(chǎn)生識(shí)別器取代基圖中的結(jié)點(diǎn)(或邊)并指定或引入器B取代組邊作為中間件連接產(chǎn)生器的輸出端和識(shí)別器的②v2中的每個(gè)結(jié)點(diǎn)v,用引理6中的一個(gè)識(shí)別輸入端,從而形成一個(gè)平面匹配網(wǎng)格。通過(guò)中間件器A取代(在圖11中,v為v2中的某一個(gè)結(jié)點(diǎn)的狀態(tài)組合取值計(jì)算匹配網(wǎng)格的 Holant量,而這個(gè)H,n2…3作為識(shí)別器的外部結(jié)點(diǎn),權(quán)重利用原始量剛好是匹配網(wǎng)格作為帶權(quán)圖的完美匹配多項(xiàng)式計(jì)算。全息算法與量子算法有一個(gè)共同點(diǎn):單值邊的權(quán)重);(0/1)用一個(gè)二維向量進(jìn)行編碼。本文對(duì)全息算法的③原始圖G=(,E,W)中的邊作為連結(jié)邊,原上述原理和計(jì)算進(jìn)行了詳細(xì)分析和解讀,文中的細(xì)始權(quán)重移到識(shí)別器輸入邊上。連結(jié)邊的權(quán)重均設(shè)為1。節(jié)和圖示可以幫助讀者理解全息算法的原理和應(yīng)圖12、圖13說(shuō)明平面匹配網(wǎng)圖的構(gòu)造用方法。Referencesstract)[C)/Proceedings of the 45th Annual IEEE Sympo-Fig 12 Original bipartite weighted planar graphsium on Foundations of Computer Science, Rome, Italy圖12原始二分帶權(quán)平面圖oct17-19,2004.[Sl.: IEEE Press,2004:306-315.L G Holographic algorithms, electronic coquium on computational complexity, TRO5-099[R]. 2005[3] Aitken A C. Determinants and matrices[M]. London<廷結(jié)Oliver and Boyd, 1951[4] Brualdi R A, Ryser H J Combinatorial matrix theory[M]Cambridge: Cambridge University Press, 1991[5] Murota K Matrices and matroids for systems analysis[M]Berlin: Springer, 2000Fig 13 Planar matchgrid (S2=(A, B,C))[6]中國(guó)煤化工 It of a planar graph inembedding generators and recognizersCNMH Gn Computing, 1975, 4圖13替換后的平面匹配網(wǎng)格(口=(A,BC)221-225146Journal of Frontiers of Computer Science and Technology計(jì)算機(jī)科學(xué)與探索2011,5(2)[7]Jansen K,KarpinskiM,Lingas A,et al.Polynomial timeConference on Computational Complexity, 2006.planar and [14] Cai Jinyi, Lu Pinyan On symmetric signatures in holo-geometric graphs[]. SIAM Journal on Computing, 2005graphic algorithms[C]/Proceedings of the 24th Annual35(1):110-119Conference on Theoretical Aspects of Computer Science[8] Jemum MR. Two-dimensional monomer-dimer systems( STACS07),2007:429440are computationally intractable[J]. Joumal of Statistical [15] Valiant L G Expressiveness of matchgates[J]. TheoreticalPhysics,1987,48(1/2):12l-134Computer Science, 2002, 289(1): 457-471[9] Vadhan S P. The complexity of counting in sparse, regular [16] Valiant L G Holographic circuits[C]/Lecture Notes inand planar graphs[]. SIAM Jourmal on Computing, 2001Computer Science 3580: Proceedings of the 32nd Inter31(2):398-427.national Colloquium on Automata, Languages and Pro-[10] Cai Jinyi, Choudhary V. Some results on matchgates andgramming, Lisbon, Portugal, July 11-15, 2005.[S I]holographic algorithms[C]/Lecture Notes in ComputerSpringer-Verlag, 2005: 1-15Science 4051: Proceedings of the 33rd International Col- [17] Valiant L G Quantum circuits that can be simulated clas-sically in polynomial time[J]. SIAM Journal on Comput-CALP),2006:703-714ng,2002,31(4):12291254[11] Cai Jinyi, Pavan A, Sivakumar D. On the hardness of [18] Bernstein E, Vazirani A Quantum complexity theory]permanent[C]/Proceedings of the 16th Annual ConferenceSIAM Journal on Computing, 1997, 26(5): 1411-1473on Theoretical Aspects of Computer Science(STACS'99), (191 Nielsen M A, Chung I L. Quantum computation andquantum information[M]. Cambridge: Cambridge Uni-[12] Cai Jinyi, Choudhary V. Valiant's Holant theorem andversity Press, 2000matchgate tensors[C]lEcture Notes in Computer Sci- [20] Su Yucai, Jiang Cuibo, Zhang Yuehui. Theory of maence 3959: Proceedings of the 3rd International Confertrix[M]. Beijing: Science Press, 2005ence on Theory and applications of Models of Computa-tion(TAMC,2006:248-261附中文參考文獻(xiàn):[3] Cai Jinyi, Choudhary V. On the theory of matchgate[20]蘇育才,姜翠波,張躍輝,矩陣?yán)碚揗北京:科學(xué)computations[CU/Proceedings of the 22nd Annual IEEE出版社,2005XU Daoyun was born in 1959. He received his M.S. degree from Guizhou University in 1988, and Ph.Ddegree from Nanjing University in 2002. Now he is a professor and doctoral supervisor at Department ofComputer Science, Guizhou University. His research interests include computability and complexity許道云1959),男,貴州安順人,1988年于貴州大學(xué)獲得碩士學(xué)位,2002年于南京大學(xué)獲得博士學(xué)位(中德聯(lián)合培養(yǎng),現(xiàn)為貴州大學(xué)計(jì)算機(jī)科學(xué)系教授、博土生導(dǎo)師,主要研究領(lǐng)域?yàn)榭捎?jì)算性與計(jì)算復(fù)雜性中國(guó)煤化工CNMHG