Testable and untestable classes of first-order formulae

摘要

In property testing, the goal is to distinguish structures that have some desired property from those that are far from having the property, based on only a small, random sample of the structure. We focus on the classification of first-order sentences according to their testability. This classification was initiated by Alon et al. (2000) [2], who showed that graph properties expressible with prefix ∃⁎∀⁎ are testable but that there is an untestable graph property expressible with quantifier prefix ∀⁎∃⁎. The main results of the present paper are as follows. We prove that all (relational) properties expressible with quantifier prefix ∃⁎∀∃⁎ (Ackermannʼs class with equality) are testable and also extend the positive result of Alon et al. (2000) [2] to relational structures using a recent result by Austin and Tao (2010) [8]. Finally, we simplify the untestable property of Alon et al. (2000) [2] and show that prefixes ∀3∃, ∀2∃∀, ∀∃∀2 and ∀∃∀∃ can express untestable graph properties when equality is allowed.