全息算法的原理及應用

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