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全息算法的原理及應用許道云貴州大學計算機科學系,貴陽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摘要:分析了全息算法的基本理論、原理和使用方法,旨在簡化對全息算法的理解并加以應用;給出了幾個實例(如平面3CNF公式的計數(shù)問題,以幫助讀者理解全息算法中的一些基本原理和方法。相關(guān)的原理和方法對解決某些組合計數(shù)問題有所幫助關(guān)鍵詞:全息算法;歸約;計數(shù)問題文獻標識碼:A中圖分類號:TP3011引言(簡稱A-問題)。即,對于給定的實例x,判定“x∈A”給定一個非空集合A,可以定義一個判定問題是否為真?傳統(tǒng)的多項式時間歸約(A≤PB)是指*The National Natural Science Foundation of China under grant Noment Foundation of Guizhou Province of china(貴州省省長基金)cYH中國煤化工學基金 the gCNMHGReceived 2010-02, Accepted 2010-06許道云:全息算法的原理及應用129判定A問題在多項式時間內(nèi)轉(zhuǎn)換到判定B問題,按此“向下歸約”的原理,如果能找到一個種從而將A-問題解的存在性判定轉(zhuǎn)換成B問題解的子(計數(shù))問題B有多項式時間算法,則借助于全息存在性判定。形式上,存在一個多項式時間可計算函歸約關(guān)系,可以構(gòu)建計數(shù)問題A的多項式時間算數(shù)f:A→B,使得:對任意的x,x∈Af(x)∈B。法。由此產(chǎn)生的算法稱為問題A的全息算法在這一轉(zhuǎn)換過程中,A問題解的一個分支轉(zhuǎn)換成全息算法的有效性基于如下結(jié)論:尋找平面圖B-問題解的一個分支。如果A≤pB,且A問題是的完美匹配數(shù)可以在多項式時間內(nèi)計算。具體來說,NP完全的,則B問題是NP難的。從20世紀70一個平面圖的完美匹配數(shù)可以轉(zhuǎn)化成計算一個矩年代Cook證明SAT問題是NP完全問題以后,以陣行列式值的平方根5。SAT問題為種子,按上述“向上歸約”的原理,只于是,全息算法的種子算法是:平面圖的完美要構(gòu)建一個多項式歸約,且證明B-問題在NP類中,匹配數(shù)的多項式時間算法。就可以證明B問題是NP完全的。用這樣的方法證全息算法的引入,解決了大量從前沒有多項式明了圖論中的許多問題(如:哈密爾頓問題、結(jié)點覆算法的計數(shù)問題,使許多原來認為很難的計數(shù)問題蓋問題等)及其他許多組合問題都是NP完全問題。有了多項式求解算法26直觀上,NP完全問題是當前計算能力不可承受的,根據(jù)“向下歸約”原理,全息算法主要用于驗NP難問題表現(xiàn)在指數(shù)時間以上的算法求解。這似證 Valiant計數(shù)問題有多項式求解算法,其主要思想乎沒有對實際應用帶來有用的結(jié)果和提供解決問是將計數(shù)問題轉(zhuǎn)換為一個平面圖的完美匹配多項題的有效方法,僅證明該問題難解。實際工作和應式計算問題。由于一個平面圖的完美匹配多項式計用中,往往利用近似算法、隨機算法等方法求近似算問題可以在多項式時間內(nèi)求解,從而原計數(shù)問題解。 Valiant在2004年提出的全息歸約及算法holo在多項式時間內(nèi)可解。完成這一轉(zhuǎn)換過程稱為全息graphic reduction and algorithms),在計算復雜性領歸約。在轉(zhuǎn)換過程中,本質(zhì)上要構(gòu)造一個平面圖作域內(nèi),解決了許多驚人的結(jié)果:許多原來認為只有為基圖,并構(gòu)造一個2階(或更高階)的可逆矩陣作指數(shù)時間算法的問題,用全息算法建立了多項式算為基矩陣,利用基矩陣對各種基本狀態(tài)進行長編碼,法1-2。利用張積表示所有可能組合,構(gòu)造恰當?shù)漠a(chǎn)生器和全息歸約是近年來計算復雜性研究領域中出現(xiàn)識別器,用產(chǎn)生器和識別器取代基圖中的結(jié)點(或的一種全新的歸約方法,全息歸約是計數(shù)問題之間邊),并指定或引入一組邊作為中間件連接產(chǎn)生器的歸約,借助歸約變換,將另一個問題的多項式求的輸出端和識別器的輸入端,從而形成一個平面匹解算法轉(zhuǎn)換到目標問題的多項式算法。配網(wǎng)格。通過中間件的狀態(tài)組合取值計算匹配網(wǎng)格般,解分支之間可能有四種關(guān)系:一對的 Holant量,而這個量剛好是匹配網(wǎng)格作為帶權(quán)圖對多、多對一、多對多。 valiant給出的全息歸約,的完美匹配多項式其特點是:將一個問題的解分支的總和數(shù)對應到另全息算法是計算復雜性領域內(nèi)一個全新的研究個問題的解分支的總和數(shù)。即,考慮所有組合可對象。 Valiant提出全息算法以來,多數(shù)研究工作是能下一個問題的完整解的和數(shù)與另一個問題的完在完善和簡化該算法的理論和方法。理解全息算法整解的和數(shù)之間的關(guān)系。于是,不同問題類的解分需要代數(shù)、組合數(shù)學、圖論、算法理論等方面的知支之間是多對多的關(guān)系。識。對一般人而言,理解、研究和應用全息算法具問題A到問題B的一個全息歸約(A≤HB淇具有有一定的難度。為了簡化和完善全息算法的思想特別意義:如果A≤B,且問題B解的和數(shù)是多項蔡進凵中國煤化工大量的工作:建立式可計算,則問題A解的和數(shù)也是多項式可計算了全CNMHG數(shù)描述體系;基于的。即問題A的解的和數(shù)有多項式算法Grassmann-Plucker等人的工作,建立了一般匹配門130Journal of Frontiers of Computer Science and Technology計算機科學與探索2011,5(2)的一個完備描述;給出了在保證完美匹配總數(shù)不變性布爾函數(shù)編碼問題。對全息算法原理的詳細分析的前提下,通過引入輔助子圖處理原圖中的交叉旨在簡化對全息算法的理解和應用,對解決其他組邊,以建立圖的平面化的多項式時間算法;研究了合問題提供幫助。涉及到的基本理論、方法和應用不同基的關(guān)系與表示能力;提出了全息算法模板還可以參考文獻[15-19等10-15類比N完全問題的證明方法,全息算法所走2基本概念和記號的路徑剛好相反:基于平面圖的完美匹配數(shù)計算在設G=(V,E,W)為一個邊帶權(quán)的無向圖,其中W多項式時間內(nèi)可解,只要證明所考慮的計數(shù)問題能為G中邊集合E上的權(quán)函數(shù)。一般假定G中無自夠全息歸約到平面圖的完美匹配計數(shù)問題,則可以回路(環(huán),即每一條邊e=(,j關(guān)聯(lián)(或稱飽和)的兩構(gòu)造出問題的多項式時間算法。這在實際中是非常個結(jié)點i、j都不相同。一個邊子集EcE所關(guān)聯(lián)的有用的。結(jié)點集合記為mc(E)。一個邊子集EcE稱為G基于這樣的思路,全息算法的研究工作主要集的一個匹配,如果E中任意兩條不同的邊1、e2中在如下幾個方面:有l(wèi)mc(e1)∩lmc(2)=②,即不同邊無公共關(guān)聯(lián)結(jié)1)全息算法理論的逐步完善,并借助于其他點。一個匹配EsE是完美的,如果lm(E)=v方法、理論對算法的描述,使算法的構(gòu)建變得更容21圖的匹配多項式易和實用。(2)借助于全息算法,尋找某些計數(shù)問題的多對于具有n個結(jié)點圖的G,引人變元集{x項式時間算法。1≤iabex-86c6c82③…⊙96c=進一步分解成為:ae8.③c8c]8b18.8引理3設T=為一個基矩陣在全息算法中,給定二階基矩陣,利用張積生421 422(取行代碼:n=(a142),P=(a,22),對正整數(shù)成一個2階變換矩陣T。,T可以分解成子矩陣k1,k2…,k1≥1,C1,C2…,C1分別為長度為2784,T。,,T。(其中k1十k2+…+k=k)聯(lián)系到量子算法中的基本思想:將一個兩矩陣U分解成若2,,2+的行向量,則有(行張積分解干二階西矩陣U1U2…,Un,而一個二階西矩陣U[C1C28.⑧C1。+++)對應一個單比特量子門,由此分解構(gòu)造一個量子電Cr 8CT8k2 88C, 8路。全息算法中一個單值可用一個二維向量p/n)作考慮取“列代碼”情形,類似地,有基準碼進行編碼;量子算法中一個單值可用一個二引理4設T=n,]為一個基矩陣維向量(op>)進行編碼。在此相似原理下,全息a22算法與量子算法具有相通之處1。取列代碼:n=41,p={2,對正整數(shù)k”4產(chǎn)生器與識別器k≥1,C,C2C分別為長度為2,24,,24的在全息算法中,匹配門r(x的兩種特例產(chǎn)生列向量,則有(列張積分解)器與識別器)是最重要的基礎概念。T+)C18C288C1=(1)產(chǎn)生器:X=Q,Y≠②;T8kC187%C2.8T0C1(2)識別器:X≠⑧,Y=。借助于引理1、引理3與引理4,將用到如下結(jié)論:當X=②,Y≠時,廠xy退化為產(chǎn)生器記為設r={41a21(為一個基矩陣,其逆矩ry),如果Y上k,稱廠→為一個k輸出產(chǎn)生器(簡中國煤化工(廠(xy)退化到一陣Tbi b=[n,p]。對兩組正整數(shù)k1,k2個長HCNMHGu(r+p)為廠y的b2l by標準標識)。許道云:全息算法的原理及應用135當X≠②,Y=必時,廠(xy)退化為識別器(記選擇適當?shù)?×2基矩陣,由此基矩陣引入一種為廠x),如果X上=k,稱廠x→為一個k輸入識二維”行代碼n、p作為基準碼類似于布爾變量別器(簡稱k-識別器)標準標識矩陣以(「(x)退化作為“一維”基準碼).驗證所有可能組合下,其計到一個長度為2的列向量u(Ix→)(稱以(x)為數(shù)行向量由n、P的張積的線性疊加表示。Fx的標準標識)所研究的問題是:u(F→y)作為函數(shù),如何在此產(chǎn)生器是在一個帶權(quán)圖G中指定一個結(jié)點子函數(shù)系”下展開計算。如:當Y上=3時,有集Y作為其輸出端口,對Y的任一個子集Z,計算u(y)=個量 PerMmatch(G-2),所有不同子集情況下,得n⑧nnn nap到a(廠)。見圖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=3為例:a(廠y)=(ao,0o0,o,o,10系數(shù)。系數(shù)用記號:wG(y,x⑧y8z)表示,其a0,10,an),分量下標是按01,2,3,4,5,6,7}中xz∈{m,p}。如:b01=G(T,p8n8p)。產(chǎn)的二進制順序從左到右排序。下標作為特征標,刪生器只考慮正迭加。即,展開系數(shù)bbou,buo除的結(jié)點子集的對應關(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)可見,{1,2,3}的子集元素“從大到小”的字典序回憶一下CNF公式的主合取范式表示與“從左到右”的0/特征標記一致。[0,1]=[n,p類似地,識別器也是在一個帶權(quán)圖G中指定01111111個結(jié)點子集X作為其輸入端口,對X的任一個子集10111111Z,計算一個量 PerfMatch(G-z),所有不同子集情110111111110況下,得到(廠x→)。見圖3。1011●保留11111101o刪除11110xvyvznvnvnFig 3 Recognizer(z=13, 4))圖3識別器(Z={3,4}Ivy-rv-yvz010Inv pvn以產(chǎn)生器的標準標識a(Fy)為例,所研究的xy"yv氣問題是:能否選擇一個2×2基矩陣,通過張積計算得到一個2*×2矩陣作為k編碼矩陣,一行代表一中國煤化工 pinp個函數(shù),k-編碼矩陣代表一個函數(shù)系(不一定正交)。CNMH GPVP要求u(廠→)能用該函數(shù)系線性疊加表示。y→ yv-] L111 LpvpJournal of Frontiers of Computer Science and technology計算機科學與探索2011,5(2)上述矩陣可作為0串的一種長編碼方式(稱為00011「n’8n標準編碼)。逆矩陣,0011_m8p注意:[0,=[n,p是“一維”基準碼,而全息0101|p8n算法中采用的是“二維”基準碼。p'⑧p對于識別器,由基矩陣引入一種“二維”列代碼n、P作為基準碼,類似考慮:(Tx→)的表示計可見4(10)0之間存套互算。如:當|X上=3時,有轉(zhuǎn)換關(guān)系。u(x→)=(n⑧n⑧n,nn⑧p,n⑧p⑧n,n②p⑧p,考慮向量(-1,0.0,1)的展開表示:設(100=0402,其中Pn⑧n,p⑧n⑧p,p②p⑧n,p⑧p⑧p)pop600(bo0b1oh1)為待定常數(shù)。而on-1-11000110n⑧0-10001⑧系數(shù)用記號:wR(fx→,xy②2)表示,其中-1000101P②P1000xy,z∈{n,p}。如:c101=wR(Fx→,P⑧n⑧p)。注意:此時x⑧y⑧z為列向量。通常,類似于mmmm所以,(4+101010h1)、(co,co0,con0,con,co,co,10,c1n)這樣的1111向量來自于原始計數(shù)問題的計數(shù)(故稱為計數(shù)標識,(,1,0)。于是,(-1,0,0,D)=n⑧n+n8P+p8n。簡稱標識)按定義,耿(Fy)、耿(x)是來自于帶權(quán)圖(產(chǎn)生器、識別器)的匹配計數(shù)表示向量(標準5計數(shù)問題的形式化描述標識本章討論一種計數(shù)問題的形式化描述。一個自然的問題是:對于同類的多個產(chǎn)生器X={x,…,x}為k個變量,其值域D的基數(shù)識別器,如何選擇一個基矩陣以此分別生成變換為d≥2。定義兩組布爾函數(shù):矩陣,要求滿足一定的約束關(guān)系下,將這些標識與協(xié)調(diào)函數(shù):a:cX→{0,1}。簡稱a-函數(shù)。標準標識的互換關(guān)系聯(lián)系起來。傾4考惠A-(10()a(4,…飛)x={寫,寫…},=12…g。0,h2=,1=其中,x1,x2…,x,形成X的一個劃分。0/°a(,,…)取值用一個長度為d的行向P量ax(X)表示。這里,n=[(-,1,(0,n,p]=[01,(1)有效函數(shù):B:cX→10,1。簡稱β-函數(shù)。nX},閏,2,,r中國煤化工2編碼矩陣:其中penCNMHG另一個劃分。月(,…)取值用一個長度為d"的列向量許道云:全息算法的原理及應用137B(xj)表示。寫=c被解釋為:結(jié)點v通過邊v,")向相鄰注意:k+k2+…+k=m+m+…+m=k。結(jié)點v傳遞信息“v著c色”。定義一個叢函數(shù):(2)引人v=4個a-函數(shù)結(jié)點函數(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)有時也記為:therwiseMass(X)=更換。a、圖9結(jié)點保留(刪除)與賦值對應關(guān)系同為行向量(或列向量)。計算轉(zhuǎn)換以后,仍然沿用 Valiant的使用方法:兩類標準①a(x,)9=m(B(x)(產(chǎn)生器B的標準標標識的計算用同一個基、同類代碼識,其中X1為B的輸出端口號集合8匹配網(wǎng)格的 Holant量②()月(x)=a(4,x)(識別器A的如果匹配網(wǎng)格圖是平面圖,則稱為平面匹配網(wǎng)標準標識,其中X為A,的輸入端口號集合)格。全息算法設計中,只考慮平面匹配網(wǎng)格,理由于是,原始計數(shù)來自于定理1。MassSum(a)=中國煤化工系到一個平面圖∑a1(x1)8a2(X2)98a2(X2GCNMHG識別器替代圖中XeNO. 1]E的結(jié)點或邊,再利用中間件關(guān)聯(lián),形成一個平面匹Journal of frontiers of Computer Science and Technology計算機科學與探索2011,5(2)配網(wǎng)格。將計數(shù)問題轉(zhuǎn)換成平面匹配網(wǎng)格的匹配計對于連結(jié)邊{,e2…},一組編碼X∈{n,p數(shù)(或匹配質(zhì)量總和)問題。對應給{e,e2,e}一組編碼指派根據(jù)連結(jié)到產(chǎn)生直觀上,產(chǎn)生器是“發(fā)射”,識別器是“吸收”。器輸出端口和識別器輸入端口的聯(lián)系,將組產(chǎn)生器和一組識別器之間,通過中間件的連通x∈{n,p作如下兩種分解關(guān)系,計數(shù)問題轉(zhuǎn)化為:在各種組合下,發(fā)射與組(1)按{,2…l連結(jié)到{B,B2,,B)的輸出合吸收之間的“有效”累計。端口的關(guān)系,通過適當調(diào)整順序,將X分解為:81匹配網(wǎng)格X=X1⑧X2②X。其中,x1,X2,…,X分別為對于一個計數(shù)問題4=(a(X1).a2(x2)…,x在B1B2B2輸出端口上的投影。a3(x2),x,(A(x1),2(X2)…月(X)),其中(2)按(,e2,,e}連結(jié)到{A,A,,A}的輸入1X1k(1≤長≤gm(≤j≤),且端口的關(guān)系,通過適當調(diào)整順序,將Ⅹ分解為∑k=∑X=X1⑧X2⑧.8Xr。其中,X1,X2,,Xr分別為X在{A1,A,…,A}輸人端口上的投影。如果存在一個2階基矩陣b=a142)_/n根據(jù)上述分解關(guān)系,對于指定的一組X的指派X∈{n,p},可以分別得到兩組o)量其逆矩陣b1=-(12=[m,p],使得如果條valG(B, X1), val (B2, X2),val(Be, X,)件成立(關(guān)于b=“的展開系數(shù)1)在基矩陣b下,存在一組產(chǎn)生器B={B1,B2,…B},使得對每一個1≤i≤g,a(X)可以valR(A, X1), valR(A,, X2),,valR(A, X,)關(guān)于b1=[m,P1的展開系數(shù))由B產(chǎn)生。即a(B1(X)=a(x。值得注意的是:如果waG(B1,X1)=1,則X出(2)在b1=b下,存在一組識別器A=A,現(xiàn)在產(chǎn)生器B的標識向量的線性和中,否則,未出A24),使得對每一個1≤j≤r,BxX)可以現(xiàn)。如果wR(A,)=1,則對出現(xiàn)在識別器A由A識別。即a(4(x)=()月(X)的標識向量的線性和中,否則,未出現(xiàn)。形式上,一個匹配網(wǎng)格由三個部分構(gòu)成:一組這就出現(xiàn)如下一致性檢測問題:對于給定的產(chǎn)生器B={B,B2…B2}、一組識別器A={A,X∈{n,p({a,2,,}一組編碼指派,檢測下式A2…,A}、一組帶權(quán)為1的連結(jié)邊C={,e2…,}。是否成立匹配網(wǎng)格用=(A,B,C)表示?！浮莣G,x)「ⅡwRA,X)=182匹配網(wǎng)格的 Holant量1≤jr如果此局部檢測成功,說明產(chǎn)生器與識別器關(guān)于對于給定的基b=(“,其逆b1=m,門1,設x∈(np一致否則,產(chǎn)生器與識別器在x下不P致在b下的匹配網(wǎng)格為定義一個量統(tǒng)計出所有的一致編碼指派。記為:g=(B,B2,…Bgl,e12…l,{A,42…A})Holant(2其中,連結(jié)邊{,e2…e}左端連結(jié)到{B1,B2,…,B}中國煤化工中的k個輸出端口,右端連結(jié)到(A,A2…,A}中的CNMH∏wR,X)k個輸入端口?！躩≤r許道云:全息算法的原理及應用143通常記為:(4)對結(jié)點和邊的有效狀態(tài)(指派)s=(sy,sg)Holant(2)=可以定義一個質(zhì)量函數(shù)mas()∑「mw0(1.x)∏wK4.x任何在s=(sy,5g)下有效的結(jié)點(或邊),都會對mas(5)貢獻一個有效因子f(sv()(或表面上, Holan(2)的求和計算中含有指數(shù)f(sg(e))。一個有效狀態(tài)(指派)的質(zhì)量mas(s)被定項。然而,可將2理解為一個帶權(quán)有向圖G并將義為所有這些結(jié)點和邊所貢獻的因子的乘積。Holant(9)的計算問題轉(zhuǎn)換為帶權(quán)有向圖G的完美(5)計數(shù)問題則是對所有有效狀態(tài)(指派)的質(zhì)匹配總和 Perfmatch(G)的計算問題。這樣,如果G量mg()求和。是平面圖,則由定理1, PerfMatch()可以在多項全息模板:對于一個給定的 valiant計數(shù)問題,式時間內(nèi)完成。這就是全息算法的本質(zhì)和精髓。求解該問題的全息模板具有如下結(jié)構(gòu):定理3對于給定的基b=[n,p],=(A,B,C)為在b下的匹配網(wǎng)格,G是Ω對應的帶權(quán)圖,則有(1)構(gòu)造一個基b=-(這里假定取“二維”編Holant(2)= PerfMatch(G)碼,類似可以使用更高維的編碼)。推論1對于給定的基b=[v,p],如果』=(2)基圖G=(,E)(平面圖)中每一個結(jié)點(A,BC)是在b下的平面匹配網(wǎng)格,則Hoan)veV和邊e=(u,y)∈E分別作如下處理在多項式時間內(nèi)可計算。①結(jié)點替換:依據(jù)狀態(tài)集S,用一個產(chǎn)生器(或識別器)替換該結(jié)點,產(chǎn)生器的端口數(shù)與結(jié)點度9全息模板數(shù)一致。為了形式化描述全息算法的基礎類型,蔡進一②邊替換:依據(jù)狀態(tài)集Sg,用一個識別器(或等人給出了一種全息算法的形式化描述—一全息模產(chǎn)生器替換邊c=(n吵),識別器帶兩個輸入端口。板12-131一個連結(jié)的產(chǎn)生器的一個輸出端口,另一個連結(jié)vaan計數(shù)問題:一↑wan計數(shù)問題是帶有ν的產(chǎn)生器的一個輸出端口。如下結(jié)構(gòu)的計數(shù)問題。(3)產(chǎn)生器和識別器的端口可適當用外部結(jié)點(1)一個平面圖G=(,E)。表示。外部連結(jié)邊{=,,…,erl連結(jié)產(chǎn)生器引出的(2)兩個狀態(tài)集Sy、SE外部(端口)結(jié)點和識別器引出的外部端口)結(jié)點結(jié)點狀態(tài)集Sv:個指派X∈{n,p}對應一個狀態(tài)s。如果廠為一個Sy:{sv:sv:v→D產(chǎn)生器,則walG(F,X)=f(s);如果廠為一個識別sv()為對結(jié)點ν有一個指派值;器,則walR(r,X)=f(s)。邊狀態(tài)集SE:(4)如果X∈{n,p}為一個無效指派,則對應SE={E:SE:E→D2于X的 Holant量為0。sg(e)為對結(jié)點e有一個指派值。例如:3CNF公式匹配網(wǎng)格中,可用2產(chǎn)生器注:兩類指派域可能不一致替換變元結(jié)點;用3-識別器替換子句結(jié)點;連結(jié)邊(3)一個局部“接受”判定標準o:判定一個給則是公式的變元子句圖中本身的邊。定的狀態(tài)指派s或sE下,局部的結(jié)點或邊是否“有效”(可接受)。對于一個k度結(jié)點,形式上,一個局10部“接受”判定標準φ表現(xiàn)為一個映射:中國煤化工Φ:y×s→(0,1}(類似于CSP問題中的約束)的計HCNMH生所有可能組合下土男仃H數(shù)問題的計算轉(zhuǎn)換14 mal of Frontiers of Computer Science and Techno計算機科學與探索2012成一個平面匹配門的標準標識矩陣計算問題。如果102全息算法設計這樣的全息歸約關(guān)系存在,并可以在多項式時間內(nèi)(1)基的選擇完成,則原計數(shù)問題在多項式時間內(nèi)可解。這是因為平面匹配門的標準標識矩陣計算問題在多項式取,n=(-11,p=(1,0)時間內(nèi)可解。(2)產(chǎn)生器匹配門設計全息歸約的目標是:尋找集合對(X,Y)和一個考慮一個局部圖:G=(,E,W,V={12},E=基矩陣,并完成標準標識矩陣以(T(xn)轉(zhuǎn)換計算過(a,2),wa,)=-1。程。求解計數(shù)問題在所有可能組合下的計數(shù)表示。通過選擇適當?shù)幕仃?將原始計數(shù)問題在多項式1·12時間內(nèi)轉(zhuǎn)換成:一個集合對(X,)下平面匹配門Fig 10 Generator with a weighted edgerxn)的標準標識矩陣(廠(x)的計算。而a(rxy)圖10一條帶權(quán)邊的產(chǎn)生器的計算可以在多項式時間內(nèi)完成,從而對于給定的產(chǎn)生器r的匹配門端口對(X,)的輸入、輸出計數(shù)問題的所有可能計數(shù)表示能夠在多項式時間端口分別為:X=②,Y={,2}。內(nèi)完成。標準標識:u(=(-1,0,0,1),對應的端口開閉為使讀者能理解全息算法的使用,本節(jié)詳細給特征函數(shù)列:00,01,10,1)出一個計數(shù)問題(# X-MATCHINGS)的全息算法的其中,1——一閉(刪除對應結(jié)點),0—開(保留對設計與分析應結(jié)點)10.1問題描述引理5存在關(guān)于基b=,n=(-1),p=# X-MATCHINGS問題輸入:一個平面帶權(quán)二部圖G=,EW),其00的產(chǎn)生器廠,使得中結(jié)點劃分為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)識別器匹配門設計定是完美匹配)考慮一個局部圖(圖11)其中,mas(M)為匹配M的質(zhì)量,定義為如下兩項之積(1)正W(e)匹配權(quán)重(-1)∑W(e)其中, unsafe(M)為M的未飽和結(jié)點集,mc()為關(guān)聯(lián)結(jié)點v的邊集合。例如,在G=V,EW)中,假定每條邊上權(quán)重Fig.1 Recognizer for weighted edges joining to a node為1,v2中每個結(jié)點的度數(shù)為4,則# MATCHINGS圖11識別一個結(jié)點關(guān)聯(lián)的帶權(quán)邊的識別器輸出G=(v,EW)的匹配數(shù),但每個匹配被賦予形中國煤化工1,w2…,叫∈F,存如(-4)的權(quán)重,其中k為該匹配未飽和V2中的結(jié)在關(guān)CNMHG點數(shù)44,F-(1,0)的識別器廠,許道云:全息算法的原理及應用145使得對所有的輸入x=x⑧x2⑧,8x∈tnp,其1l結(jié)束語系數(shù)值wR(廠,x)具有如下性質(zhì):全息算法主要用于驗證 Valiant計數(shù)問題有多valR(廠,x)=項式求解算法,其主要思想是將計數(shù)問題轉(zhuǎn)換為一(+w2+…+w)個平面圖的完美匹配多項式計算問題。由于一個平耳=P,V≠Dx=川面圖的完美匹配多項式計算問題可以在多項式時otherwise間內(nèi)求解,從而原計數(shù)問題在多項式時間內(nèi)可解(4)全息歸約構(gòu)造完成這一轉(zhuǎn)換過程稱為全息歸約。在轉(zhuǎn)換過程中對于平面帶權(quán)二部圖G=(V,E,W),其中結(jié)點本質(zhì)上要構(gòu)造一個平面圖作為基圖,并構(gòu)造一個2劃分為V=VUV2,邊權(quán)函數(shù)為W:E→R,階(或更高階)的可逆矩陣作為基矩陣,利用基矩陣vv∈V)deg(v)=2]。對各種基本狀態(tài)進行長編碼,利用張積表示所有可構(gòu)造如下平面匹配網(wǎng)格=(A,B,C):能組合,構(gòu)造恰當?shù)漠a(chǎn)生器和識別器,用產(chǎn)生器和①v中的每個結(jié)點v,用引理5中的一個產(chǎn)生識別器取代基圖中的結(jié)點(或邊)并指定或引入器B取代組邊作為中間件連接產(chǎn)生器的輸出端和識別器的②v2中的每個結(jié)點v,用引理6中的一個識別輸入端,從而形成一個平面匹配網(wǎng)格。通過中間件器A取代(在圖11中,v為v2中的某一個結(jié)點的狀態(tài)組合取值計算匹配網(wǎng)格的 Holant量,而這個H,n2…3作為識別器的外部結(jié)點,權(quán)重利用原始量剛好是匹配網(wǎng)格作為帶權(quán)圖的完美匹配多項式計算。全息算法與量子算法有一個共同點:單值邊的權(quán)重);(0/1)用一個二維向量進行編碼。本文對全息算法的③原始圖G=(,E,W)中的邊作為連結(jié)邊,原上述原理和計算進行了詳細分析和解讀,文中的細始權(quán)重移到識別器輸入邊上。連結(jié)邊的權(quán)重均設為1。節(jié)和圖示可以幫助讀者理解全息算法的原理和應圖12、圖13說明平面匹配網(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]中國煤化工 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計算機科學與探索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附中文參考文獻:[3] Cai Jinyi, Choudhary V. On the theory of matchgate[20]蘇育才,姜翠波,張躍輝,矩陣理論M北京:科學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年于貴州大學獲得碩士學位,2002年于南京大學獲得博士學位(中德聯(lián)合培養(yǎng),現(xiàn)為貴州大學計算機科學系教授、博土生導師,主要研究領域為可計算性與計算復雜性中國煤化工CNMHG