Nondeterministic graph property testing
arXiv:1202.5337 · doi:10.1017/S0963548313000205
Abstract
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 certificates 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.
Version 2: 11 pages; we allow orientation in the certificate, describe new applications