Baltic J. Modern Computing, Vol. 4 (2016), No. 4, pp. 736–752

The Kahr–Moore–Wang Class Contains
Untestable Properties
Charles JORDAN? and Thomas ZEUGMANN??
Division of Computer Science, Hokkaido University, N-14, W-9, Sapporo, Japanskip@ist.hokudai.ac.jp, thomas@ist.hokudai.ac.jp

Abstract. Property testing is a kind of randomized approximation in which one takes
a small, random sample of a structure and wishes to determine whether the structure satisfies some property or is far from satisfying the property. We focus on thetestability of classes of first-order expressible properties, and in particular, on the classification of prefix-vocabulary classes for testability. The main result is the untestabilityof [∀∃∀, (0, 1)]= . We also show that this class remains untestable without equality inat least one model of testing. These classes are well-known and (at least one is) minimal for untestability. We discuss what is currently known about the classification for
testability and briefly compare it to other classifications.
Keywords: property testing, logic, randomized algorithms, Kahr–Moore–Wang class

1

Introduction

Testing a property can be viewed as a form of approximation where we tradeaccuracy for efficiency. As far as we are aware, de Leeuw et al. (1956) first formalized probabilistic machines. They showed that such machines cannot compute
uncomputable properties under reasonable assumptions, but mention the possibility that probabilistic machines could perhaps be more efficient than deterministic machines. This topic attracted considerable attention including Gill (1977).
Early examples of such results were presented by Freivalds (1977), (1979) including his matrix multiplication checker.
In property testing, we take a random sample of some large structure and wish
to distinguish between the case that it has some desired property and the casethat it is far from having the property. We focus on the testability of first-order?

Supported by JSPS Grant Nos. 15H00847, ‘Exploring the Limits of Computation’(ELC), and 16H02785.
??
Supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas underGrant No. 21013001.

2

C. Jordan and T. Zeugmann

expressible properties, and in particular on the classification of prefix-vocabularyclasses of first-order logic for testability.
Rubinfeld and Sudan (1996) and Blum et al. (1993) introduced the notion ofproperty testing in the context of formal verification. The basic idea was soon
extended by Goldreich et al. (1998), who represented graphs as binary functions
and focused on testing graph properties. We omit a detailed history of testing,see the introduction to testing graph properties by Goldreich (2010), two surveys
by Ron (2008), (2009), and older surveys by Fischer (2001) and Ron (2001).
We are particularly interested in the testability of properties expressible insubclasses of first-order logic, and review relevant work in Subsection 1.1.
Here, we show that there exist untestable graph properties expressible withquantifier prefix ∀∃∀ when equality is allowed (see Section 3 for a formal statement). In addition, we use a variation of that proof to show that this prefix
remains untestable in at least one of our models even when equality is forbidden. We suspect that the class is untestable without equality in all of our models.
Taking into account the related work described in Subsection 1.1 and using
the notation of Definition 7, the current classification for testability is the following (cf. Jordan and Zeugmann (2012)). We omit the result for [∀∃∀, (0, 1)]
because it may depend on the choice of model.
– Testable classes
1. Monadic first-order logic: [all, (ω)]= .
2. Ackermann’s class with equality: [∃∗ ∀∃∗ , all]= .
3. Ramsey’s class: [∃∗ ∀∗ , all]= .
– Untestable classes
1. [∀3 ∃, (0, 1)]= .
2. [∀∃∀, (0, 1)]= .
We are especially interested in determining the testability of variants of theGödel class (i.e., classes whose prefix contains at least ∀2 ∃) as this would suffice tocomplete the classification for the special case of predicate logic with equality.
The above classification is consistent with several other well-known classifications, such as that for the finite model property (see, e.g., Chapter 6 of Börger
et al. (1997), for docility (or finite satisfiability, see Kolaitis and Vardi (2000))
and for associated 0-1 laws for fragments of existential second-order logic (see
Kolaitis and Vardi (2000)). It would be interesting to know if the classification
for testability coincides with one of these classifications.
The rest of the paper is organized as follows: First, we review related work in
Subsection 1.1. Definitions and notation are in Section 2. The proof of untestability for [∀∃∀, (0, 1)]= is presented in Section 3, while the case without equality
is considered in Section 4.
1.1

Related Work

Alon et al. (2001) proved that the regular languages are testable, implying thatmonadic first-order is testable given the well-known results of Büchi (1960) orThe Kahr–Moore–Wang Class Contains Untestable Properties

3

McNaughton and Papert (1971). Alon et al. (2000) were the first to directly
consider the classification problem for testability, restricted to properties of
undirected, loop-free graphs. They showed the testability of all such properties expressible by prenex sentences with quantifier prefix ∃∗ ∀∗ , and also provedthat there exists an untestable property expressible with quantifier prefix ∀∗ ∃∗(examining the proof shows that ∀12 ∃5 suffices).
These are (restrictions of) well-known classes. Jordan and Zeugmann (2012)extended the positive result to the full Ramsey’s class ([∃∗ ∀∗ , all]= ), proved thetestability of Ackermann’s class with equality ([∃∗ ∀∃∗ , all]= ), and sharpened thenegative result to prefixes ∀3 ∃, ∀2 ∃∀, ∀∃∀∃ and ∀∃∀2 (on directed graphs withequality). This paper sharpens these last three prefixes and proves that ∀∃∀ isa minimal prefix class for untestability. This particular class is the restriction of
the Kahr–Moore–Wang (1962) class to directed graphs.
It is easy to show that [∀∃∀, (0, 1)] (even without equality) has infinity axioms1 . Vedø (1997) showed that a 0-1 law does not hold for second-order existential logic when the first-order part is in this class (again, even without equality).
The current paper sharpens some (prefixes ∀2 ∃∀, ∀∃∀∃, ∀∃∀2 ) of the resultsof Jordan and Zeugmann (2012) and so we briefly outline the improvement thatallows us to minimize the prefix considered. The untestable property considered
there is closely related to the untestable property of Alon et al. (2000), but modified to minimize the number of quantifiers used. These properties are essentiallyfirst-order expressible versions of checking an explicitly given isomorphism between two graphs2 . In fact, restricting the properties to checking an explicitly
given isomorphism between undirected, bipartite graphs maintains hardness fortesting. See Figure 1(a) for an example where the goal is to check whether the
directed edges give an isomorphism between the two bipartite subgraphs. However, graph isomorphism seems to require one to discuss at least four vertices
simultaneously (because one wishes to state that an edge is present iff its image
is present and the edges are disjoint in general).

(a) A graph with Pb(b) A graph with Pe(c) A graph with Pf

Fig. 1. Properties Pb , Pe and Pf
1
2

An infinity axiom is a sentence that has only infinite models.
Graph isomorphism is generally hard for testing, cf. Fischer and Matsliah (2008).

4

C. Jordan and T. Zeugmann

Sharing one of the partitions would seem to remove the need for four quantifiers. See Figure 1(b) for an example where the goal is again to check whether
the directed edges give an isomorphism between the two halves of the graph.
The resulting property is perhaps closer to a variant of function isomorphism,
e.g., for functions f, g : {1, . . . , n} → {0, 1}n where the bit i of f (j) is 1 if there
is an edge from j in the leftmost partition to i in the middle partition and likewise for g(j) and the right partition. This property is not first-order expressible,
but there is a somewhat tedious first-order encoding that is sufficiently similar.
Figure 1(c) gives an example of this first-order property; details are in Section 3.
The connection with function isomorphism allows us to leverage recent workon the testability of (Boolean) function isomorphism and use recent ideas andtechniques from Alon and Blais (2010) to prove Lemma 2. In Section 4, we use
a variation of this property that removes the use of equality.

2

Preliminaries

The goal in property testing is always to distinguish structures that have someproperty from those that are far from having the property. Here, we focus on
first-order expressible properties of directed graphs and so we begin with thenecessary definitions.
Definition 1. A graph is an ordered pair G = (V, E), where V is a finite set
and E ⊆ V × V a binary relation defined on V .
Let N = {1, 2, 3, . . .} denote the set of all natural numbers. We generally
identify V with the first n natural numbers [n] := {1, . . . , n} and call #(G) :=|V | = n the size of a graph G. Furthermore, let G n be the set of graphs of size n
and let G := ∪n≥0 G n be the set of all (finite) graphs. Note that our graphs are
directed and may contain loops.
A property P ⊆ G of graphs is any set of graphs. We are particularly interested in first-order expressible properties. Our logic is a basic first-order predicate
logic with equality. There are no function or constant symbols. We focus on firstorder properties of graphs, and so the only predicate symbol (besides the special
symbol =) is the binary edge symbol E.
A sentence ϕ defines a property in the natural way,Pϕ := {G | G ∈ G, G |= ϕ} .
We require a distance between graphs and properties, which we define in thefollowing way: We denote the symmetric difference of sets M and N by M 4 N
and let E A and E B be the edge predicates of graphs A and B, respectively.
Definition 2. Let n ∈ N, let A = (V, E A ) and B = (V, E B ) be two graphs
defined such that |V | = n. The distance between A and B isdist(A, B) := |E A 4 E B |/n2 .

The Kahr–Moore–Wang Class Contains Untestable Properties

5

The distance generalizes to properties, dist(A, P ) := minB∈P dist(A, B). Definition 2 results in a typical model of testing based on the dense graph model
introduced by Goldreich et al. (1998). We now proceed to the remaining testing
definitions.
Definition 3. An ε-tester for property P is a randomized algorithm that makes
queries for the existence of edges in a graph A. The tester must accept withprobability at least 2/3 if A has P and must reject with probability at least 2/3
if dist(A, P ) ≥ ε.
Definition 4. Property P is called testable if there is some function c(ε) andfor every ε > 0, an ε-tester for P such that the tester makes at most c(ε) queries.
Note that the query complexity is bounded by a function that does notdepend on the size of the graphs. We allow different ε-testers for each ε > 0 andso this is a non-uniform model. However, we are focused on proving untestability
and our results hold even in the non-uniform case.
Next, we will define indistinguishability, a relation on properties introduced
by Alon et al. (2000) that preserves testability. However, testers can focus onloops and distinguish between structures that have an asymptotically small difference (because the number of loops is asymptotically dominated by the numberof non-loops). We therefore begin with an alternative definition of distance. In
the following, ⊕ denotes exclusive-or.
Definition 5. Let n ∈ N, n ≥ 2, and let U be any universe such that |U | = n.
Furthermore, let A = (U, E A ) and B = (U, E B ) be any two graphs with universe U . For notational convenience, letx | x ∈ U and E A (x, x) ⊕ E B (x, x), and
d1 (A, B) :=n(x1 , x2 ) | x1 , x2 ∈ U, x1 6= x2 , and E A (x1 , x2 ) ⊕ E B (x1 , x2 ).
d2 (A, B) :=n(n − 1)
The mr-distance between A and B is
mrdist(A, B) := max {d1 (A, B), d2 (A, B)} .
Definition 6. Two properties P and Q of graphs are indistinguishable if they
are closed under isomorphisms and for every ε > 0 there exists an Nε such thatfor any graph A with universe of size n ≥ Nε , if A has P then mrdist(A, Q) ≤ ε
and if A has Q then mrdist(A, P ) ≤ ε.
An important property of indistinguishability is that it preserves testability.
The proof of the following is analogous to that given in Alon et al. (2000).
Lemma 1. If P and Q are indistinguishable, then P is testable if and only if Q
is testable.

6

C. Jordan and T. Zeugmann

In fact, as the proof constructs an ε-tester for P by iterating an ε/2-tester
for Q three times, one can also relate the query complexities of P and Q.
Definition 5 (mrdist) is a distance measure that can be used in place ofDefinition 2 (dist) when defining testability. The resulting model makes testing
strictly more difficult than using dist, see Jordan and Zeugmann (2012). We
refer to properties that are testable using mrdist as mr-testable. In Section 3,
we prove the untestability of ∀∃∀ with equality in both models3 . However, ourproof for the class without equality (cf. Section 4) is restricted to proving it is
not mr-testable. We suspect that this restriction can be removed.
Many proofs of hardness for testability rely on Yao’s Principle (1977), aninterpretation of von Neumann’s minimax theorem for randomized computation.
For completeness, we state the version that we use.
Principle 1 (Yao’s Principle). If there is an ε ∈ (0, 1) and a distribution
over G n such that all deterministic testers with complexity c have an error-rate
greater than 1/3 for property P , then property P is not testable with complexity c.
The definition of “testable” is of course our usual one involving random
testers. In general, one seeks to show that for sufficiently large n and someincreasing function c := c(n), there is a distribution of inputs such that all
deterministic testers with complexity c have error-rates greater than 1/3.
Finally, we briefly define the notation we use to specify prefix-vocabularyclasses. See Börger et al. (1997) for details and related material.
Definition 7. Let Π be a string over the four-character alphabet {∃, ∀, ∃∗ , ∀∗ }.
Then [Π, (0, 1)]= is the set of sentences in prenex normal form which satisfy thefollowing conditions:
1. The quantifier prefix is contained in the regular language given by Π (fortechnical reasons, one usually treats ∃ and ∀ as matching the relevant quantifier and also the empty string).
2. There are zero (0) monadic predicate symbols.
3. In addition to the equality predicate (=), there is at most one (1) binary
predicate symbol.
4. There are no other predicate symbols.
That is, [Π, (0, 1)]= is the set of prenex sentences in the logic defined above whose
quantifier prefixes match Π. If the second component of the specification is all,then conditions two and three are removed (any number of predicate symbols
with any arities are acceptable).

3

The Case with Equality

Our goal in this section is Theorem 1.
3

The proof assumes the use of dist. However, testing with mrdist is strictly moredifficult and so the proof also implies untestability using mrdist.

The Kahr–Moore–Wang Class Contains Untestable Properties

7

Theorem 1. The prefix class [∀∃∀, (0, 1)]= is not testable.
We begin by outlining the proof. First, we define Pf , a property expressible
in the class [∀∃∀, (0, 1)]= which, as described in Subsection 1.1, is in some sensea somewhat tedious but first-order expressible variant of checking (explicit) isomorphism of undirected bipartite graphs in tripartite graphs. We then define avariant P2 , in which the isomorphism is not explicitly given and we must test
whether there exists some suitable isomorphism. Although this increases thecomplexity of deciding the problem from checking an isomorphism to finding
one, it does not change hardness for testing. We show that P2 and Pf are indistinguishable and so P2 is testable√iff Pf is testable. Finally, we prove directlythat P2 is untestable, even with o( n) queries, using an argument based on a
recent proof by Alon and Blais (2010).
Proof (Theorem 1). We begin by defining Pf . Formally, it is the set of graphs
satisfying the following conjunction of four clauses (see Figure 1(c) for an example):∀x∃y∀z : { ((¬E(x, x) ∧ ¬E(z, z) ∧ x 6= z) → E(x, z))∧(E(x, x) → (E(x, y) ∧ ¬E(y, y) ∧ [(¬E(z, z) ∧ E(x, z)) → y = z]))∧∧(¬E(x, x) → (E(y, x) ∧ E(y, y) ∧ [(E(z, z) ∧ E(z, x)) → y = z]))((E(x, x) ∧ E(z, z)) → [¬E(y, y) ∧ E(x, y) ∧ (E(x, z) ↔ E(y, z))]) }A graph satisfies this formula if the following conditions are all satisfied:
1. The nodes without loops form a complete subgraph.
2. For every node x with a loop, there is exactly one y without a loop such that
there is an edge from x to y.
3. For every node y without a loop, there is exactly one x with a loop such that
there is an edge from x to y.
4. For all nodes x, z with loops, and y the unique node without a loop suchthat E(x, y), it holds that E(x, z) iff E(y, z).
Property P2 below is similar to Pf , except that the isomorphism is not explicitly given.
Definition 8. A graph G = (V, E) has P2 if it satisfies the following conditions:
1. There is a partition4 V1 , V2 ⊆ V such that |V1 | = |V2 |, there are loops(E(x, x)) on all x ∈ V1 and no loops (¬E(x, x)) for all x ∈ V2 .
2. The nodes without loops form a complete subgraph.
3. There are no edges from a node with a loop to a node without a loop.
4. There exists a bijection b : V1 → V2 such that if x, z have loops, then E(x, z)
iff E(b(x), z).
It is not difficult to show that properties Pf and P2 are indistinguishable.
4

V1 , V2 partition V if V1 ∩ V2 = ∅ and V1 ∪ V2 = V .

8

C. Jordan and T. Zeugmann

Claim 1. Properties Pf and P2 are indistinguishable.
Proof (Claim 1). Let ε > 0 be arbitrary and let Nε = ε−1 . Assume that G has
property P2 and that #(G) > Nε . We will show that mrdist(G, Pf ) < ε.
Graph G has P2 and so there is a bijection satisfying Condition 4 of Definition 8. We therefore add the edges E(i, b(i)) making the isomorphism (from V1
to V2 ) explicit. The resulting graph Gf has Pf .
We have made exactly n/2 modifications, all to non-loops, and n − 1 ≥ Nε ,so mrdist(G, Pf ) ≤ mrdist(G, Gf ) = 1/2(n − 1) < ε.
The converse is analogous; given a G that has Pf , simply remove the n/2
edges from loops to non-loops after using them to construct a suitable bijection b.
tu
Properties Pf and P2 are indistinguishable and so (by Lemma 1), it suffices
to show that P2 is is √untestable. Lemma 2 below is stronger than necessary, andactually implies a Ω( n) lower bound for testing Pf per the discussion following
Lemma 1.
tu√Lemma 2. Fix 0 < ε < 1/2. Any ε-tester for P2 must perform Ω( n) queries.
Proof (Lemma 2). The proof is via Yao’s Principle (cf. Principle 1), and so wedefine two distributions, Dno and Dyes and show that all deterministic testers
have an error-rate greater than 1/3 for property P2 when the input is chosenrandomly from Dno with probability 1/2 and from Dyes with probability 1/2.
In the following, we consider a distribution over graphs of sufficiently large
size 2n, and an arbitrarily fixed partition of the vertices into V1 and V2 suchthat |V1 | = |V2 | = n (e.g., let the vertices be the integers V := [2n], V1 := [n],and V2 := V \V1 ).
We begin with Dno , defined as the following distribution:
1. Place a loop on each vertex in V1 and place no loops in V2 .
2. Place each possible edge (except loops) in V1 × V1 and V2 × V1 uniformly
and independently with probability 1/2.
That is, Dno is the uniform distribution of graphs (with this particular partition)satisfying the first three conditions of P2 .
Next, we define Dyes as the following:
1. Choose uniformly a random bijection π : V1 → V2 .
2. Place a loop on each vertex in V1 and place no loops in V2 .
3. For each possible edge (i, j 6= i) ∈ V1 × V1 , uniformly and independently
place both (i, j) and (π(i), j) with probability 1/2 (otherwise place neither).
It is easy to see that Dyes generates only positive instances. Next, we showthat Dno generates negative instances with high probability.
Lemma 3. Fix 0 < ε < 1/2 and let n be sufficiently large. Then,Pr [dist(G, P2 ) ≤ ε] = o(1) .

G∼DnoThe Kahr–Moore–Wang Class Contains Untestable Properties

9

Proof (Lemma 3). The distribution Dno is the uniform distribution over graphsof size 2n with a particular partition satisfying the first three conditions of P2 .
Let Gε be the set of graphs G0 of size 2n satisfying these conditions and suchthat dist(G0 , P2 ) ≤ ε (regardless of the partition).
Counting the number of such graphs shows|Gε | ≤

 
dε2n2 e 
X 2n2 2n n(n−1) H()2n2
2n n(n−1)
2
n!
≤
2
n!2
,
i
n
n
i=0

where H(ε) := −ε log ε − (1 − ε) log(1 − ε) is the binary entropy function (cf.
Lemma 16.19 in Flum and Grohe (2006) for the bound on the summation).
2
Distribution Dno produces each of 2n(n−1) 2n graphs with equal probability,
and so
 
2
2
|Gε |
2n
Pr [dist(G, P2 ) ≤ ε] ≤ n(n−1)+n2 ≤n!2H()2n /2n
G∼Dno
n
2
≈

4n n!2H()2n
√
πn2n2

2

= o(1) .

The approximation is asymptotically tight, which suffices.

tu

We have shown that Dyes generates only positive instances and that (withhigh probability) Dno generates instances that are ε-far from P2 . Next, we showthat (again, with√ high probability) the two distributions look the same to testers
making only o( n) queries.
The proof is similar to a proof by Alon and Blais (2010). We begin by defining
two random processes, Pno and Pyes , which answer queries from testers andgenerate instances according to Dno and Dyes , respectively.
Process Pno is defined in the following way:
1. Choose uniformly a random bijection π : V1 → V2 .
2. Intercept all queries from the tester and respond as follows:(a) To queries E(i, i) with i ∈ V1 : respond 1.
(b) To queries E(i, i) with i ∈ V2 : respond 0.
(c) To queries E(i, j) with i ∈ V1 and j ∈ V2 : respond 0.
(d) To queries E(i, j) with i 6= j ∈ V1 : quit if we have queried E(π(i), j),otherwise respond 1 or 0 randomly with probability 1/2 in each case.
(e) To queries E(i, j) with i ∈ V2 and j ∈ V1 : quit if we have queriedE(π −1 (i), j), otherwise respond 1 or 0 randomly with probability 1/2 ineach case.
3. When the process has quit or the tester has finished its queries, complete
the generated instance in the following way: First, fix the edges that werequeried according to our answer. Next, place loops on each vertex in V1 , noloops in V2 and no edges from V1 to V2 . Place each remaining possible edge,
place it (uniformly, independently) with probability 1/2, ignoring π.

10

C. Jordan and T. Zeugmann

We define Pyes in the same way, except for the final step. When Pyes quits or
the tester finishes, it fixes the edges that were queried according to its answers,
and also fixes the corresponding edges (when relevant) according to π. Moreprecisely, for each fixed E(i, j) with i 6= j ∈ V1 , we also fix E(π(i), j) and for
fixed E(i, j) with i ∈ V2 , j ∈ V1 , we also fix E(π −1 (i), j), in both cases the sameas our response to E(i, j) (not randomly). The remaining edges are placed asin Pno .
Note that Pno generates instances according to Dno and Pyes generates instances according to Dyes . In addition, Pyes and Pno behave identically until they
quit or answer all queries. In particular, if a tester does not cause the process toquit, the distribution of responses of its queries is identical for√ the two processes.
We show that, with high probability, a tester that makes o( n) queries does notcause either process to quit.
√
Lemma 4. Let T be a deterministic tester which makes o( n) queries, andlet T interact with Pyes or Pno . In both cases,
Pr [T causes the process to quit] = o(1) .
Proof (Lemma 4). The condition causing the process to quit is identical in Pyes
and Pno . The probability that any pair of queries E(i, j) and E(i0 , j 0 ) cause theprocess to quit is at mostPr [i0 = π(i) or i = π(i0 )] ≤(n − 1)!
= 1/n .
n!

√
The tester makes at most o( n) queries and so√
Pr [T causes the process to quit] ≤ o( n)2 O(1/n) = o(1) .
tu√
Any deterministic tester T which makes o( n) queries can only distinguishbetween Dyes and Dno with probability o(1), but it must accept Dyes with probability 2/3, and reject Dno with probability 2/3 − o(1). It is impossible for T tosatisfy both conditions, and the lemma follows from Principle 1.
tu

4

The Case without Equality

In Section 3, we proved that [∀∃∀, (0, 1)]= is untestable. The formula proved
untestable contains equality, and so we now consider the class without equality.
The main result in this section is Theorem 2, stating that [∀∃∀, (0, 1)] is not mrtestable. Although this seems to be a tradeoff between the presence of equality
and the “degree” of testability, we suspect that this class is not testable undereither definition. The proof is very similar to the proof above.
Theorem√ 2. There are properties in [∀∃∀, (0, 1)] that are not mr-testable, evengiven o( n) queries.

The Kahr–Moore–Wang Class Contains Untestable Properties

11

Proof (Theorem 2). The proof is similar to the proof of Theorem 1. We will
begin by defining a property Pf that is expressible in our class. We will thendefine a property P which is indistinguishable from Pf , and use Yao’s Principle
to show that P is not mr-testable.
A graph has property Pf if it satisfies the following conditions:
1. For every x with a loop, there is an outgoing edge to at least one y withouta loop.
2. For every x without a loop, there is an incoming edge from at least one y
without a loop.
3. There are no edges between vertices without loops.
4. For every x with a loop, there is an edge to at least one y without a loop
such that for all z with loops, the following holds: There is a directed edge
from y to z iff there are an odd number5 of directed edges between x and z.
5. For every x without a loop, there is an incoming edge from at least one ywith a loop such that for all z with loops, the following holds: There is adirected edge from x to z iff there are an odd number of directed edges
between y and z.
More formally, Pf is the set of graphs that satisfy the following formula:∀x∃y∀z :∧{ (E(x, x) → (¬E(y, y) ∧ E(x, y)))(¬E(x, x) → (E(y, y) ∧ E(y, x)))∧((¬E(x, x) ∧ ¬E(z, z)) → ¬E(x, z))∧∧((E(x, x) ∧ E(z, z)) → ((E(x, z) ⊕ E(z, x)) ↔ E(y, z)))((¬E(x, x) ∧ E(z, z)) → ((E(y, z) ⊕ E(z, y)) ↔ E(x, z))) }Next, we define a property P that we will show to be indistinguishable
from Pf . A graph has property P if it satisfies the following conditions:
1. There is a partition of the vertices into (non-empty) V1 , V2 .
2. All vertices in V1 have loops and no vertices in V2 have loops.
3. There are no edges in V2 × V2 .
4. There exist functions f : V1 → V2 and g : V2 → V1 satisfying the following:
For all x, z ∈ V1 , there is an edge from f (x) to z iff there are an odd numberof directed edges between x and z. For all x ∈ V2 and z ∈ V1 , there is anedge from x to z iff there are an odd number of directed edges between g(x)and z.
It is not difficult to show that P and Pf are indistinguishable.
Lemma 5. Properties P and Pf are indistinguishable.
5

There is an odd number of edges between x and z if there is a directed edge from x
to z or from z to x, but not both. Note that a loop is counted as an even number ofedges.

12

C. Jordan and T. Zeugmann

Proof (Lemma 5). Let G be graph with property Pf and let ε > 0 be arbitrarily
fixed. Then, G also has property P , that is mrdist(G, P ) = 0. In the otherdirection, if the graph G has property P , then we can satisfy property Pf byadding at most O(n) (non-loop) edges from x to f (x) and g −1 (y) to y. Thus,tumrdist(G, Pf ) ≤ O(n)/Θ(n2 ) = o(1) < ε for sufficiently large graphs.
Indistinguishability preserves testability (cf. Lemma 1) and so it suffices toshow that P is untestable.
Lemma 6 below is stronger than necessary and ac√tually implies a Ω( n) lower bound for testing Pf per the discussion following
Lemma 1.
tuLemma 6.√There is an 0 < ε < 1/2 such that any mr-style ε-tester for P must
perform Ω( n) queries.
Proof (Lemma 6). The proof is via Yao’s Principle (cf. Principle 1) and so wemust define a distribution of inputs and show that all deterministic ε-testers
have an error rate greater than 1/3 for P on inputs from the distribution. For
our distribution, we will draw from a distribution Dno with probability 1/2 andfrom a distribution Dyes with probability 1/2.
In the following, we consider distributions over graphs with sufficiently large
vertex set [2n] and an arbitrarily fixed partition of the vertices into V1 and V2
such that |V1 | = |V2 | = n.
We begin with Dno , defined as the following distribution:
1. Place loops on all vertices in V1 and no loops in V2 .
2. For each ordered pair in V1 × V2 , place a directed edge with probability 1/2.
3. For each unordered pair {i, j}, i, j ∈ V1 and i 6= j, with probability 1/2 placeno edge, and with probability 1/2 place a single directed edge, from i to j
if i ≤ j and from j to i if j ≤ i.
4. For each ordered pair in V2 ×V1 , with probability 1/2 place the directed edge
and with probability 1/2 do not.
Note that Dno is the uniform distribution of graphs that satisfy the following
conditions:
1. The vertex set is [2n] and the vertices with loops follow the given partition.
2. There are no undirected edges between vertices with loops (when a loop is
not considered an undirected edge).
3. There are no edges between vertices without loops.
4. All directed edges (i, j) between vertices with loops satisfy i ≤ j.
Next, we define Dyes .
1. Place loops on all vertices in V1 and no loops in V2 .
2. For each ordered pair in V1 × V2 , place a directed edge with probability 1/2.
3. Choose uniformly a random bijection π : V1 → V2 .
4. For each unordered pair in (i, j 6= i) ∈ V1 × V1 , with probability 1/2 dothe following: Place directed edges (π(i), j) and (π(j), i), and then placeeither (i, j) (if i ≤ j) or (j, i) (if j ≤ i). Otherwise, do not place any edges
right now.

The Kahr–Moore–Wang Class Contains Untestable Properties

13

Distribution Dyes generates only positive instances for P . Now, we show thatwith high probability, Dno generates instances that are ε-far.
Lemma 7. Let ε > 0 be sufficiently small and n be sufficiently large. Then,Pr [mrdist(G, P ) ≤ ε] = o(1) .

G∼Dno

Proof (Lemma 7). Distribution Dno is the uniform distribution over graphs ofsize 2n with a fixed partition V1 , V2 satisfying the following:
1. All vertices in V1 have loops and no vertices in V2 have loops.
2. There are no undirected edges between vertices with loops.
3. There are no edges between vertices without loops.
4. All directed edges (x, y) between vertices with loops satisfy x ≤ y.
We want a small upper-bound on the probability of a graph being drawn
from Dno that is not ε-far from P . Since Dno is the uniform distribution over acertain class of graphs, this probability is{G | G ∼ Dno , mrdist(G, P ) ≤ ε}.
{G | G ∼ Dno }n
2
2
The number of distinct graphs produced by Dno is 2( 2 ) 22n = 22.5n −n/2 .
Let G2n be the set of graphs with vertices [2n] that have property P and are
not ε-far from all graphs in Dno . Then,Pb4εn2 c 4n2 |G2n | i=0i
Pr [mrdist(G, P ) ≤ ε] ≤
.
(1)
G∼Dno
22.5n2 −n/2
Note that any graph G that is not ε-far from all graphs in Dno must haveloops on n − εn ≤ j ≤ n + εn vertices. Therefore,n+εn
X 2n j|G2n | ≤4(2) 2j(2n−j) j 2n−jjj=n−εn 2
2n 2(n+εn2 2 )+(n+εn) +(n+εn) log (n+εn) .
(2)≤ (2εn + 1)n√
Using the (asymptotically tight) estimate 2n≈ 4n / πn, we see that (2) isnapproximately(2εn + 1) 2n+(n+εn)2 +(n+εn)(n+εn−1)+(n+εn) log(n+εn)√2.
πn
Pbε4n2 c 4n2 2Combining this with Inequality (1) and using that i=0≤ 2H(ε)4n ,iwhere H(ε) = −ε log ε − (1 − ε) log(1 − ε) is the binary entropy function (cf.
Lemma 16.19 in Flum and Grohe (2006)), we get
Pr [mrdist(G, P ) ≤ ε]

G∼Dno

≤

2εn + 1 −n2 /2+4H(ε)n2 +3/2n+2(ε2 +ε)n2 +εn+(n+εn) log (n+εn)√2= o(1) ,πnbecause the −n2 /2 in the exponent dominates when ε is sufficiently small.

t
u

14

C. Jordan and T. Zeugmann

We have shown that Dyes generates only positive instances and, with highprobability, Dno generates ε-far instances. Next, we show that, with√high probability, the two distributions look identical to testers making only o( n) queries.
The proof is similar to a proof by Alon and Blais (2010).
We begin by defining two random processes, Pno and Pyes , which answer
queries from testers and generate instances according to Dno and Dyes , respectively.
Process Pno is defined in the following way:
1. Choose uniformly a random bijection π : V1 → V2 .
2. Intercept all queries from the tester and respond as follows:(a) To queries E(i, i) with i ∈ V1 , respond 1.
(b) To queries E(i, i) with i ∈ V2 , respond 0.
(c) To queries E(i, j) with i ∈ V2 , j ∈ V2 , respond 0.
(d) To queries E(i, j) with i ∈ V1 , j ∈ V2 , randomly respond 1 or 0 withprobability 1/2 in each case.
(e) To queries E(i, j) with i > j ∈ V1 , respond 0.
(f) To queries E(i, j) with i < j ∈ V1 , quit if we have queried E(π(i), j)or E(π(j), i). Otherwise randomly respond 1 or 0 with probability 1/2
in each case.
(g) To queries E(i, j) with i ∈ V2 , j ∈ V1 , quit if we have queried E(π −1 (i), j)or E(j, π −1 (i)). Otherwise randomly respond 1 or 0 with probability 1/2
in each case.
3. When the process has quit, or the tester has finished its queries, complete
the generated instance in the following way:
First, fix the edges that were queried according to our answers. Next, placeloops on all vertices in V1 , no loops in V2 and no edges internal to V2 . Placeeach edge in V1 × V2 uniformly and independently with probability 1/2. For
each remaining possible edge (i, j) ∈ V1 × V1 , place the edge uniformly andindependently with probability 1/2 if i < j and do not place the edge if
i > j. For each remaining possible edge in V2 × V1 , place the edge uniformly
and independently with probability 1/2 (ignoring π).
We define Pyes in the same way, except for the final step. When Pyes quits or
the tester finishes, it fixes the edges that were queried according to its answers,
and also fixes the corresponding edges (when relevant) according to π. Moreprecisely, for each fixed E(i, j) with i 6= j ∈ V1 , we also fix E(π(i), j) andE(j, π(i)), and for fixed E(i, j) such that i ∈ V2 , j 6= π −1 (i) ∈ V1 , we also fix
E(π −1 (i), j) and E(j, π −1 (i)), in both cases according to our previous decision.
The remaining edges are placed as in Pno .
Note that Pno generates instances according to Dno and Pyes generates instances according to Dno . In addition, Pyes and Pno behave identically until they
quit or answer all queries. In particular, if a tester does not cause the process toquit, the distribution of responses to queries is identical for√ the two processes.
We show that, with high probability, a tester that makes o( n) queries does notcause either process to quit.

The Kahr–Moore–Wang Class Contains Untestable Properties

15√
Lemma 8. Let T be a deterministic tester which makes o( n) queries, andlet T interact with Pyes or Pno . In both cases,
Pr[T causes the process to quit] = o(1) .
Proof (Lemma 8). The condition causing the process to quit is identical in Pyes
and Pno . The probability that any fixed pair of queries E(i, j) and E(i0 , j 0 ) cause
the process to quit is at mostPr[i0 = π(i) or i0 = π(j)] ≤2(n − 1)!
= 2/n .
n!

√
The tester makes at most o( n) queries and so√
Pr[T causes the process to quit] ≤ o( n)2 O(1/n) = o(1) .
tu√
Any deterministic tester T which makes o( n) queries can only distinguishbetween Dyes and Dno with probability o(1), but it must accept Dyes with probability at least 2/3 and reject Dno with probability at least 2/3 − o(1). It is
impossible for T to satisfy both conditions, so the lemma follows from Principle 1.
tu5

Conclusions

Property testing is a kind of randomized approximation, where we take a small,random sample of a structure and seek to determine whether the structure has adesired property or is far from having the property. We focused on the classification problem for testability, wherein we seek to determine exactly which prefix
vocabulary classes are testable and which are not.
In particular, we focused on the the testability of first-order properties expressible with quantifier prefix ∀∃∀. In Section 3, we showed that this prefix can
express untestable (directed) graph properties when equality is available. Then,in Section 4 we considered the class without equality. There, we showed that
this class remains mr-untestable, however testability using dist remains open.
We suspect that this class remains untestable using dist. These results sharpen
some of the results of Jordan and Zeugmann (2012).
As mentioned in Subsection 1.1, the current classification for testability
closely resembles several other classifications (e.g., those for the finite model
property, docility and associated second-order 0-1 laws) and it would be interesting to determine whether it coincides with one of these. In particular,
determining the testability of variants of the Gödel class would complete theclassification for the special case of predicate logic with equality.

16

C. Jordan and T. Zeugmann

Acknowledgments
We are very thankful to Rūsiņš Freivalds for hosting us as visitors and for the
many enlightening discussions on probabilistic algorithms we enjoyed during
these stays in Riga. We’re also grateful to Neil Immerman for pointing out thatremoving equality in our untestable properties does not really change the “spirit”
of why they are untestable. Section 4 formalizes this for prefix ∀∃∀. We suspectthat the mr-untestable property given there is also untestable when using dist,
and that a similar argument can be used to remove equality from the untestableproperty with prefix ∀3 ∃ given in Jordan and Zeugmann (2012). Finally, we
thank Hiro Ito for pointing out an omission in a previous version of the proof of
Lemma 2 (cf. Jordan and Zeugmann (2011)).

References
Alon, N. and Blais, E. (2010). Testing Boolean function isomorphism. In Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques,
13th International Workshop, APPROX 2010, and 14th International Workshop,
RANDOM 2010, Barcelona, Spain, September 2010, Proceedings, volume 6302 of
Lecture Notes in Computer Science, pages 394–405. Springer.
Alon, N., Fischer, E., Krivelevich, M., and Szegedy, M. (2000). Efficient testing of large
graphs. Combinatorica, 20(4):451–476.
Alon, N., Krivelevich, M., Newman, I., and Szegedy, M. (2001). Regular languages aretestable with a constant number of queries. SIAM J. Comput., 30(6):1842–1862.
Blum, M., Luby, M., and Rubinfeld, R. (1993). Self-testing/correcting with applications
to numerical problems. J. of Comput. Syst. Sci., 47(3):549–595.
Börger, E., Grädel, E., and Gurevich, Y. (1997). The Classical Decision Problem.
Springer-Verlag.
Büchi, J. R. (1960). Weak second-order arithmetic and finite-automata. Z. Math. Logik
Grundlagen Math., 6:66–92.
Fischer, E. (2001). The art of uninformed decisions. Bulletin of the European Association for Theoretical Computer Science, 75:97–126. Columns: Computational
Complexity.
Fischer, E. and Matsliah, A. (2008). Testing graph isomorphism. SIAM J. Comput.,
38(1):207–225.
Flum, J. and Grohe, M. (2006). Parametrized Complexity Theory. Springer.
Freivalds, R. (1977). Probabilistic machines can use less running time. In Gilchrist, B.,
editor, Information Processing 77, Proceedings of the IFIP Congress 77, Toronto,
Canada, August 8-12, 1977, pages 839–842, North-Holland.
Freivalds, R. (1979). Fast probabilistic algorithms. In Mathematical Foundations ofComputer Science 1979, Proceedings, 8th Symposium, Olomouc, Czechoslovakia,
September 3-7, 1979, volume 74 of Lecture Notes in Computer Science, pages 57–
69. Springer-Verlag.
Gill, J. (1977). Computational complexity of probabilistic Turing machines. SIAM J.
Comput., 6(4):675–695.
Goldreich, O. (2010). Introduction to testing graph properties. Technical Report
TR10-082, Electronic Colloquium on Computational Complexity (ECCC).
Goldreich, O., Goldwasser, S., and Ron, D. (1998). Property testing and its connection
to learning and approximation. J. ACM, 45(4):653–750.

The Kahr–Moore–Wang Class Contains Untestable Properties

17

Jordan, C. and Zeugmann, T. (2011). Untestable properties in the Kahr–Moore–Wang
class. In Beklemishev, L. D. and de Queiroz, R., editors, Logic, Language, Information and Computation, 18th International Workshop, WoLLIC 2011, Philadelphia,
PA, USA, May 18-21, 2011, Proceedings, volume 6642 of Lecture Notes in Artificial
Intelligence, pages 176–186. Springer, 2011.
Jordan, C. and Zeugmann, T. (2012). Testable and untestable classes of first-orderformulae. J. of Comput. Syst. Sci., 78(5):1557–1578.
Kahr, A. S., Moore, E. F., and Wang, H. (1962). Entscheidungsproblem reduced tothe ∀∃∀ case. Proc. Nat. Acad. Sci. U.S.A., 48:365–377.
Kolaitis, P. G. and Vardi, M. Y. (2000). 0-1 laws for fragments of existential secondorder logic: A survey. In Nielsen, M. and Rovan, B., editors, Mathematical Foundations of Computer Science 2000, 25th International Symposium, MFCS 2000,
Bratislava, Slovakia, August/September 2000, Proceedings, volume 1893 of Lecture
Notes in Computer Science, pages 84–98. Springer.
de Leeuw, K., Moore, E.F., Shannon, C. E., and Shapiro, N. (1965). Computability
by probabilistic machines. In Shannon, C. E. and McCarthy, J., editors, Automata
Studies, pages 183–212. Princeton University Press, Princeton, NJ.
McNaughton, R. and Papert, S. (1971). Counter-Free Automata. M.I.T. Press.
Ron, D. (2001). Property testing. In Rajasekaran, S., Pardalos, P. M., Reif, J. H.,
and Rolim, J., editors, Handbook of Randomized Computing, volume II, chapter 15,
pages 597–649. Kluwer Academic Publishers.
Ron, D. (2008). Property testing: A learning theory perspective. Found. Trends Mach.
Learn., 1(3):307–402.
Ron, D. (2009). Algorithmic and analysis techniques in property testing. Found. Trends
Theor. Comput. Sci., 5(2):73–205.
Rubinfeld, R. and Sudan, M. (1996). Robust characterizations of polynomials withapplications to program testing. SIAM J. Comput., 25(2):252–271.
Vedø, A. (1997). Asymptotic probabilities for second-order existential Kahr-MooreWang sentences. J. Symbolic Logic, 62(1):304–319.
Yao, A. C.-C. (1977). Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science, pages
222–227. IEEE Computer Society.