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

Abstract: A property testing algorithm is required to highly probably distinguish the case that the input has predeter- mined property II and the case that the input is afar from having the property,for any given parameter s. If there is a property testing algorithm for II such that its query complexity is independent of the input size parameter n, II is called testable. Let H be a graph, H-free is the property of containing no copy of H. For any connected graph H, Uoldreich and Ron show that H-free is testable in bounded degree model. In adjacency matrix model, it proves that F}free is tester ble,for any given H.

Key words: Property testing, Query complexity, Regularity lemma, Regularity r}duction,hestability