二元关系的性质测试及其复杂性分析

本文介绍了性质测试的基本原理,分析了用性质测试方法解决参数化问题的可行性,并将同构性质进行了参数化。研究了二元关系的性质测试以及参数化框架同构性质的测试问题,对固定的距离参数,证明了测试复杂性低于标准判定程序的复杂性。

大图中子图的可测性质

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