本文介绍了性质测试的基本原理,分析了用性质测试方法解决参数化问题的可行性,并将同构性质进行了参数化。研究了二元关系的性质测试以及参数化框架同构性质的测试问题,对固定的距离参数,证明了测试复杂性低于标准判定程序的复杂性。
The basic principle of property testing is introduced, the possibility of using property testing methods to solve parameterized problems is analyzed, and then the isomorphism properties are parameterized. It studies the property testing of binary relations and parameterized framework isomorphism properties. For a fixed distance parameter, it proves that the testing complexity is better than the complexity of exact decision procedures for every property studied.