全息算法的原理及应用

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公式的计数问题,以帮助读者理解全息算法中的一些基本原理和方法。相关的原理和方法对解决某些组合计数问题有所帮助关键词:全息算法;归约;计数问题文献标识码:A中图分类号:TP3011引言(简称A-问题)。即,对于给定的实例x,判定“x∈A”给定一个非空集合A,可以定义一个判定问题是否为真?传统的多项式时间归约(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问题在多项式时间内转换到判定B问题,按此“向下归约”的原理,如果能找到一个种从而将A-问题解的存在性判定转换成B问题解的子(计数)问题B有多项式时间算法,则借助于全息存在性判定。形式上,存在一个多项式时间可计算函归约关系,可以构建计数问题A的多项式时间算数f:A→B,使得:对任意的x,x∈Af(x)∈B。法。由此产生的算法称为问题A的全息算法在这一转换过程中,A问题解的一个分支转换成全息算法的有效性基于如下结论:寻找平面图B-问题解的一个分支。如果A≤pB,且A问题是的完美匹配数可以在多项式时间内计算。具体来说,NP完全的,则B问题是NP难的。从20世纪70一个平面图的完美匹配数可以转化成计算一个矩年代Cook证明SAT问题是NP完全问题以后,以阵行列式值的平方根5。SAT问题为种子,按上述“向上归约”的原理,只于是,全息算法的种子算法是:平面图的完美要构建一个多项式归约,且证明B-问题在NP类中,匹配数的多项式时间算法。就可以证明B问题是NP完全的。用这样的方法证全息算法的引入,解决了大量从前没有多项式明了图论中的许多问题(如:哈密尔顿问题、结点覆算法的计数问题,使许多原来认为很难的计数问题盖问题等)及其他许多组合问题都是NP完全问题。有了多项式求解算法26直观上,NP完全问题是当前计算能力不可承受的,根据“向下归约”原理,全息算法主要用于验NP难问题表现在指数时间以上的算法求解。这似证 Valiant计数问题有多项式求解算法,其主要思想乎没有对实际应用带来有用的结果和提供解决问是将计数问题转换为一个平面图的完美匹配多项题的有效方法,仅证明该问题难解。实际工作和应式计算问题。由于一个平面图的完美匹配多项式计用中,往往利用近似算法、随机算法等方法求近似算问题可以在多项式时间内求解,从而原计数问题解。 Valiant在2004年提出的全息归约及算法holo在多项式时间内可解。完成这一转换过程称为全息graphic reduction and algorithms),在计算复杂性领归约。在转换过程中,本质上要构造一个平面图作域内,解决了许多惊人的结果:许多原来认为只有为基图,并构造一个2阶(或更高阶)的可逆矩阵作指数时间算法的问题,用全息算法建立了多项式算为基矩阵,利用基矩阵对各种基本状态进行长编码,法1-2。利用张积表示所有可能组合,构造恰当的产生器和全息归约是近年来计算复杂性研究领域中出现识别器,用产生器和识别器取代基图中的结点(或的一种全新的归约方法,全息归约是计数问题之间边),并指定或引入一组边作为中间件连接产生器的归约,借助归约变换,将另一个问题的多项式求的输出端和识别器的输入端,从而形成一个平面匹解算法转换到目标问题的多项式算法。配网格。通过中间件的状态组合取值计算匹配网格般,解分支之间可能有四种关系:一对的 Holant量,而这个量刚好是匹配网格作为带权图对多、多对一、多对多。 valiant给出的全息归约,的完美匹配多项式其特点是:将一个问题的解分支的总和数对应到另全息算法是计算复杂性领域内一个全新的研究个问题的解分支的总和数。即,考虑所有组合可对象。 Valiant提出全息算法以来,多数研究工作是能下一个问题的完整解的和数与另一个问题的完在完善和简化该算法的理论和方法。理解全息算法整解的和数之间的关系。于是,不同问题类的解分需要代数、组合数学、图论、算法理论等方面的知支之间是多对多的关系。识。对一般人而言,理解、研究和应用全息算法具问题A到问题B的一个全息归约(A≤HB淇具有有一定的难度。为了简化和完善全息算法的思想特别意义:如果A≤B,且问题B解的和数是多项蔡进凵中国煤化工大量的工作:建立式可计算,则问题A解的和数也是多项式可计算了全CNMHG数描述体系;基于的。即问题A的解的和数有多项式算法Grassmann-Plucker等人的工作,建立了一般匹配门130Journal of Frontiers of Computer Science and Technology计算机科学与探索2011,5(2)的一个完备描述;给出了在保证完美匹配总数不变性布尔函数编码问题。对全息算法原理的详细分析的前提下,通过引入辅助子图处理原图中的交叉旨在简化对全息算法的理解和应用,对解决其他组边,以建立图的平面化的多项式时间算法;研究了合问题提供帮助。涉及到的基本理论、方法和应用不同基的关系与表示能力;提出了全息算法模板还可以参考文献[15-19等10-15类比N完全问题的证明方法,全息算法所走2基本概念和记号的路径刚好相反:基于平面图的完美匹配数计算在设G=(V,E,W)为一个边带权的无向图,其中W多项式时间内可解,只要证明所考虑的计数问题能为G中边集合E上的权函数。一般假定G中无自够全息归约到平面图的完美匹配计数问题,则可以回路(环,即每一条边e=(,j关联(或称饱和)的两构造出问题的多项式时间算法。这在实际中是非常个结点i、j都不相同。一个边子集EcE所关联的有用的。结点集合记为mc(E)。一个边子集EcE称为G基于这样的思路,全息算法的研究工作主要集的一个匹配,如果E中任意两条不同的边1、e2中在如下几个方面:有lmc(e1)∩lmc(2)=②,即不同边无公共关联结1)全息算法理论的逐步完善,并借助于其他点。一个匹配EsE是完美的,如果lm(E)=v方法、理论对算法的描述,使算法的构建变得更容21图的匹配多项式易和实用。(2)借助于全息算法,寻找某些计数问题的多对于具有n个结点图的G,引人变元集{x项式时间算法。1≤iabex-86c6c82③…⊙96c=进一步分解成为:ae8.③c8c]8b18.8引理3设T=为一个基矩阵在全息算法中,给定二阶基矩阵,利用张积生421 422(取行代码:n=(a142),P=(a,22),对正整数成一个2阶变换矩阵T。,T可以分解成子矩阵k1,k2…,k1≥1,C1,C2…,C1分别为长度为2784,T。,,T。(其中k1十k2+…+k=k)联系到量子算法中的基本思想:将一个两矩阵U分解成若2,,2+的行向量,则有(行张积分解干二阶西矩阵U1U2…,Un,而一个二阶西矩阵U[C1C28.⑧C1。+++)对应一个单比特量子门,由此分解构造一个量子电Cr 8CT8k2 88C, 8路。全息算法中一个单值可用一个二维向量p/n)作考虑取“列代码”情形,类似地,有基准码进行编码;量子算法中一个单值可用一个二引理4设T=n,]为一个基矩阵维向量(op>)进行编码。在此相似原理下,全息a22算法与量子算法具有相通之处1。取列代码:n=41,p={2,对正整数k”4产生器与识别器k≥1,C,C2C分别为长度为2,24,,24的在全息算法中,匹配门r(x的两种特例产生列向量,则有(列张积分解)器与识别器)是最重要的基础概念。T+)C18C288C1=(1)产生器:X=Q,Y≠②;T8kC187%C2.8T0C1(2)识别器:X≠⑧,Y=。借助于引理1、引理3与引理4,将用到如下结论:当X=②,Y≠时,厂xy退化为产生器记为设r={41a21(为一个基矩阵,其逆矩ry),如果Y上k,称厂→为一个k输出产生器(简中国煤化工(厂(xy)退化到一阵Tbi b=[n,p]。对两组正整数k1,k2个长HCNMHGu(r+p)为厂y的b2l by标准标识)。许道云:全息算法的原理及应用135当X≠②,Y=必时,厂(xy)退化为识别器(记选择适当的2×2基矩阵,由此基矩阵引入一种为厂x),如果X上=k,称厂x→为一个k输入识二维”行代码n、p作为基准码类似于布尔变量别器(简称k-识别器)标准标识矩阵以(「(x)退化作为“一维”基准码).验证所有可能组合下,其计到一个长度为2的列向量u(Ix→)(称以(x)为数行向量由n、P的张积的线性叠加表示。Fx的标准标识)所研究的问题是:u(F→y)作为函数,如何在此产生器是在一个带权图G中指定一个结点子函数系”下展开计算。如:当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产生器(Z=(2)其中,b0,bon,bno,bn,b,bog,hn0,b1视为展开以k=3为例:a(厂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)。产的二进制顺序从左到右排序。下标作为特征标,删生器只考虑正迭加。即,展开系数bbou,buo除的结点子集的对应关系为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)可见,{1,2,3}的子集元素“从大到小”的字典序回忆一下CNF公式的主合取范式表示与“从左到右”的0/特征标记一致。[0,1]=[n,p类似地,识别器也是在一个带权图G中指定01111111个结点子集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以产生器的标准标识a(Fy)为例,所研究的xy"yv气问题是:能否选择一个2×2基矩阵,通过张积计算得到一个2*×2矩阵作为k编码矩阵,一行代表一中国煤化工 pinp个函数,k-编码矩阵代表一个函数系(不一定正交)。CNMH GPVP要求u(厂→)能用该函数系线性叠加表示。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时,有转换关系。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)为待定常数。而on-1-11000110n⑧0-10001⑧系数用记号: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向量来自于原始计数问题的计数(故称为计数标识,(,1,0)。于是,(-1,0,0,D)=n⑧n+n8P+p8n。简称标识)按定义,耿(Fy)、耿(x)是来自于带权图(产生器、识别器)的匹配计数表示向量(标准5计数问题的形式化描述标识本章讨论一种计数问题的形式化描述。一个自然的问题是:对于同类的多个产生器X={x,…,x}为k个变量,其值域D的基数识别器,如何选择一个基矩阵以此分别生成变换为d≥2。定义两组布尔函数:矩阵,要求满足一定的约束关系下,将这些标识与协调函数:a:cX→{0,1}。简称a-函数。标准标识的互换关系联系起来。倾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)有效函数:B:cX→10,1。简称β-函数。nX},闰,2,,r中国煤化工2编码矩阵:其中penCNMHG另一个划分。月(,…)取值用一个长度为d"的列向量许道云:全息算法的原理及应用137B(xj)表示。写=c被解释为:结点v通过边v,")向相邻注意:k+k2+…+k=m+m+…+m=k。结点v传递信息“v着c色”。定义一个丛函数:(2)引人v=4个a-函数结点函数):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结点保留(删除)与赋值对应关系同为行向量(或列向量)。计算转换以后,仍然沿用 Valiant的使用方法:两类标准①a(x,)9=m(B(x)(产生器B的标准标标识的计算用同一个基、同类代码识,其中X1为B的输出端口号集合8匹配网格的 Holant量②()月(x)=a(4,x)(识别器A的如果匹配网格图是平面图,则称为平面匹配网标准标识,其中X为A,的输入端口号集合)格。全息算法设计中,只考虑平面匹配网格,理由于是,原始计数来自于定理1。MassSum(a)=中国煤化工系到一个平面图∑a1(x1)8a2(X2)98a2(X2GCNMHG识别器替代图中XeNO. 1]E的结点或边,再利用中间件关联,形成一个平面匹Journal of frontiers of Computer Science and Technology计算机科学与探索2011,5(2)配网格。将计数问题转换成平面匹配网格的匹配计对于连结边{,e2…},一组编码X∈{n,p数(或匹配质量总和)问题。对应给{e,e2,e}一组编码指派根据连结到产生直观上,产生器是“发射”,识别器是“吸收”。器输出端口和识别器输入端口的联系,将组产生器和一组识别器之间,通过中间件的连通x∈{n,p作如下两种分解关系,计数问题转化为:在各种组合下,发射与组(1)按{,2…l连结到{B,B2,,B)的输出合吸收之间的“有效”累计。端口的关系,通过适当调整顺序,将X分解为:81匹配网格X=X1⑧X2②X。其中,x1,X2,…,X分别为对于一个计数问题4=(a(X1).a2(x2)…,x在B1B2B2输出端口上的投影。a3(x2),x,(A(x1),2(X2)…月(X)),其中(2)按(,e2,,e}连结到{A,A,,A}的输入1X1k(1≤长≤gm(≤j≤),且端口的关系,通过适当调整顺序,将Ⅹ分解为∑k=∑X=X1⑧X2⑧.8Xr。其中,X1,X2,,Xr分别为X在{A1,A,…,A}输人端口上的投影。如果存在一个2阶基矩阵b=a142)_/n根据上述分解关系,对于指定的一组X的指派X∈{n,p},可以分别得到两组o)量其逆矩阵b1=-(12=[m,p],使得如果条valG(B, X1), val (B2, X2),val(Be, X,)件成立(关于b=“的展开系数1)在基矩阵b下,存在一组产生器B={B1,B2,…B},使得对每一个1≤i≤g,a(X)可以valR(A, X1), valR(A,, X2),,valR(A, X,)关于b1=[m,P1的展开系数)由B产生。即a(B1(X)=a(x。值得注意的是:如果waG(B1,X1)=1,则X出(2)在b1=b下,存在一组识别器A=A,现在产生器B的标识向量的线性和中,否则,未出A24),使得对每一个1≤j≤r,BxX)可以现。如果wR(A,)=1,则对出现在识别器A由A识别。即a(4(x)=()月(X)的标识向量的线性和中,否则,未出现。形式上,一个匹配网格由三个部分构成:一组这就出现如下一致性检测问题:对于给定的产生器B={B,B2…B2}、一组识别器A={A,X∈{n,p({a,2,,}一组编码指派,检测下式A2…,A}、一组带权为1的连结边C={,e2…,}。是否成立匹配网格用=(A,B,C)表示。「∏wG,x)「ⅡwRA,X)=182匹配网格的 Holant量1≤jr如果此局部检测成功,说明产生器与识别器关于对于给定的基b=(“,其逆b1=m,门1,设x∈(np一致否则,产生器与识别器在x下不P致在b下的匹配网格为定义一个量统计出所有的一致编码指派。记为:g=(B,B2,…Bgl,e12…l,{A,42…A})Holant(2其中,连结边{,e2…e}左端连结到{B1,B2,…,B}中国煤化工中的k个输出端口,右端连结到(A,A2…,A}中的CNMH∏wR,X)k个输入端口。≤j≤r许道云:全息算法的原理及应用143通常记为:(4)对结点和边的有效状态(指派)s=(sy,sg)Holant(2)=可以定义一个质量函数mas()∑「mw0(1.x)∏wK4.x任何在s=(sy,5g)下有效的结点(或边),都会对mas(5)贡献一个有效因子f(sv()(或表面上, Holan(2)的求和计算中含有指数f(sg(e))。一个有效状态(指派)的质量mas(s)被定项。然而,可将2理解为一个带权有向图G并将义为所有这些结点和边所贡献的因子的乘积。Holant(9)的计算问题转换为带权有向图G的完美(5)计数问题则是对所有有效状态(指派)的质匹配总和 Perfmatch(G)的计算问题。这样,如果G量mg()求和。是平面图,则由定理1, PerfMatch()可以在多项全息模板:对于一个给定的 valiant计数问题,式时间内完成。这就是全息算法的本质和精髓。求解该问题的全息模板具有如下结构:定理3对于给定的基b=[n,p],=(A,B,C)为在b下的匹配网格,G是Ω对应的带权图,则有(1)构造一个基b=-(这里假定取“二维”编Holant(2)= PerfMatch(G)码,类似可以使用更高维的编码)。推论1对于给定的基b=[v,p],如果』=(2)基图G=(,E)(平面图)中每一个结点(A,BC)是在b下的平面匹配网格,则Hoan)veV和边e=(u,y)∈E分别作如下处理在多项式时间内可计算。①结点替换:依据状态集S,用一个产生器(或识别器)替换该结点,产生器的端口数与结点度9全息模板数一致。为了形式化描述全息算法的基础类型,蔡进一②边替换:依据状态集Sg,用一个识别器(或等人给出了一种全息算法的形式化描述—一全息模产生器替换边c=(n吵),识别器带两个输入端口。板12-131一个连结的产生器的一个输出端口,另一个连结vaan计数问题:一↑wan计数问题是带有ν的产生器的一个输出端口。如下结构的计数问题。(3)产生器和识别器的端口可适当用外部结点(1)一个平面图G=(,E)。表示。外部连结边{=,,…,erl连结产生器引出的(2)两个状态集Sy、SE外部(端口)结点和识别器引出的外部端口)结点结点状态集Sv:个指派X∈{n,p}对应一个状态s。如果厂为一个Sy:{sv:sv:v→D产生器,则walG(F,X)=f(s);如果厂为一个识别sv()为对结点ν有一个指派值;器,则walR(r,X)=f(s)。边状态集SE:(4)如果X∈{n,p}为一个无效指派,则对应SE={E:SE:E→D2于X的 Holant量为0。sg(e)为对结点e有一个指派值。例如:3CNF公式匹配网格中,可用2产生器注:两类指派域可能不一致替换变元结点;用3-识别器替换子句结点;连结边(3)一个局部“接受”判定标准o:判定一个给则是公式的变元子句图中本身的边。定的状态指派s或sE下,局部的结点或边是否“有效”(可接受)。对于一个k度结点,形式上,一个局10部“接受”判定标准φ表现为一个映射:中国煤化工Φ:y×s→(0,1}(类似于CSP问题中的约束)的计HCNMH生所有可能组合下土男仃H数问题的计算转换14 mal of Frontiers of Computer Science and Techno计算机科学与探索2012成一个平面匹配门的标准标识矩阵计算问题。如果102全息算法设计这样的全息归约关系存在,并可以在多项式时间内(1)基的选择完成,则原计数问题在多项式时间内可解。这是因为平面匹配门的标准标识矩阵计算问题在多项式取,n=(-11,p=(1,0)时间内可解。(2)产生器匹配门设计全息归约的目标是:寻找集合对(X,Y)和一个考虑一个局部图:G=(,E,W,V={12},E=基矩阵,并完成标准标识矩阵以(T(xn)转换计算过(a,2),wa,)=-1。程。求解计数问题在所有可能组合下的计数表示。通过选择适当的基矩阵,将原始计数问题在多项式1·12时间内转换成:一个集合对(X,)下平面匹配门Fig 10 Generator with a weighted edgerxn)的标准标识矩阵(厂(x)的计算。而a(rxy)图10一条带权边的产生器的计算可以在多项式时间内完成,从而对于给定的产生器r的匹配门端口对(X,)的输入、输出计数问题的所有可能计数表示能够在多项式时间端口分别为:X=②,Y={,2}。内完成。标准标识:u(=(-1,0,0,1),对应的端口开闭为使读者能理解全息算法的使用,本节详细给特征函数列:00,01,10,1)出一个计数问题(# X-MATCHINGS)的全息算法的其中,1——一闭(删除对应结点),0—开(保留对设计与分析应结点)10.1问题描述引理5存在关于基b=,n=(-1),p=# X-MATCHINGS问题输入:一个平面带权二部图G=,EW),其00的产生器厂,使得中结点划分为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)识别器匹配门设计定是完美匹配)考虑一个局部图(图11)其中,mas(M)为匹配M的质量,定义为如下两项之积(1)正W(e)匹配权重(-1)∑W(e)其中, unsafe(M)为M的未饱和结点集,mc()为关联结点v的边集合。例如,在G=V,EW)中,假定每条边上权重Fig.1 Recognizer for weighted edges joining to a node为1,v2中每个结点的度数为4,则# MATCHINGS图11识别一个结点关联的带权边的识别器输出G=(v,EW)的匹配数,但每个匹配被赋予形中国煤化工1,w2…,叫∈F,存如(-4)的权重,其中k为该匹配未饱和V2中的结在关CNMHG点数44,F-(1,0)的识别器厂,许道云:全息算法的原理及应用145使得对所有的输入x=x⑧x2⑧,8x∈tnp,其1l结束语系数值wR(厂,x)具有如下性质:全息算法主要用于验证 Valiant计数问题有多valR(厂,x)=项式求解算法,其主要思想是将计数问题转换为一(+w2+…+w)个平面图的完美匹配多项式计算问题。由于一个平耳=P,V≠Dx=川面图的完美匹配多项式计算问题可以在多项式时otherwise间内求解,从而原计数问题在多项式时间内可解(4)全息归约构造完成这一转换过程称为全息归约。在转换过程中对于平面带权二部图G=(V,E,W),其中结点本质上要构造一个平面图作为基图,并构造一个2划分为V=VUV2,边权函数为W:E→R,阶(或更高阶)的可逆矩阵作为基矩阵,利用基矩阵vv∈V)deg(v)=2]。对各种基本状态进行长编码,利用张积表示所有可构造如下平面匹配网格=(A,B,C):能组合,构造恰当的产生器和识别器,用产生器和①v中的每个结点v,用引理5中的一个产生识别器取代基图中的结点(或边)并指定或引入器B取代组边作为中间件连接产生器的输出端和识别器的②v2中的每个结点v,用引理6中的一个识别输入端,从而形成一个平面匹配网格。通过中间件器A取代(在图11中,v为v2中的某一个结点的状态组合取值计算匹配网格的 Holant量,而这个H,n2…3作为识别器的外部结点,权重利用原始量刚好是匹配网格作为带权图的完美匹配多项式计算。全息算法与量子算法有一个共同点:单值边的权重);(0/1)用一个二维向量进行编码。本文对全息算法的③原始图G=(,E,W)中的边作为连结边,原上述原理和计算进行了详细分析和解读,文中的细始权重移到识别器输入边上。连结边的权重均设为1。节和图示可以帮助读者理解全息算法的原理和应图12、图13说明平面匹配网图的构造用方法。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替换后的平面匹配网格(口=(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年于南京大学获得博士学位(中德联合培养,现为贵州大学计算机科学系教授、博土生导师,主要研究领域为可计算性与计算复杂性中国煤化工CNMHG