A property of finite graphs is called nondeterministically testable if it has a “certificate” such that once the certificate is specified, its correctness can be verified by random local testing. In this paper we study certificatees that consist of one or more unary and/or binary relations on the nodes, in the case of dense graphs. Using the theory of graph limits, we prove that nondeterministically testable properties are also deterministically testable.
['László Lovász', 'Katalin Vesztergombi']
Nondeterministic graph property testing