大图中子图的可测性质

对于给定的距离参数。，性质测试算法a需以高概率正确地区分给定的对象具备预定性质ii与二远离性质ii。若存在ii的测试算法a满足其询问复杂性独立于规模参数n，则称ii是可测的。设h是一个图，性质仔了)℃。为不含井子图的图所构成的集合。在有界度模型中，goldreich与ron证明了对任意连通图h，性质仔力℃。是可测的}s}。在邻接矩阵模型中，证明了对任意图h，不管其连通与否，性质件厂re。是可测的。