作者：韦立 许道云 王正才性质测试询问复杂性正则引理正则归约可测试性
摘要：对于给定的距离参数ε,性质测试算法A需以高概率正确地区分给定的对象具备预定性质Π与ε-远离性质Π。若存在Π的测试算法A满足其询问复杂性独立于规模参数n,则称Π是可测的。设H是一个图,性质H-free为不含H-子图的图所构成的集合。在有界度模型中,Goldreich与Ron证明了对任意连通图H,性质H-free是可测的[9]。在邻接矩阵模型中,证明了对任意图H,不管其连通与否,性质H-free是可测的。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
