大图中子图的可测性质

摘要：

对于给定的距离参数ε,性质测试算法A需以高概率正确地区分给定的对象具备预定性质Ⅱ与ε-远离性质Ⅱ.若存在Ⅱ的测试算法A满足其询问复杂性独立于规模参数n,则称Ⅱ是可测的.设H是一个图,性质H-free为不含H-子图的图所构成的集合.在有界度模型中,Goldreich与Ron证明了对任意连通图H,性质H-free是可测的[9].在邻接矩阵模型中,证明了对任意图H,不管其连通与否,性质H-free是可测的.

关键词：性质测试、询问复杂性、正则引理、正则归约、可测试性

所属期刊栏目：39

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61262006;贵州省研究生创新基金2010005

在线出版日期：2013-01-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：228-232