Abstract:

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.

Key words: property test;binary relation;parameterized;isomorphism;query complexity