Techniques for Reversing the Order of Quantifiers

Question

It is well-known that in general, the order of universal and existential quantifiers cannot be reversed. In other words, for a general logical formula $\phi(\cdot,\cdot)$,

$(\forall x)(\exists y) \phi(x,y) \quad \not\Leftrightarrow \quad (\exists y)(\forall x) \phi(x,y)$

On the other hand, we know the right-hand side is more restrictive than the left-hand side; that is, $(\exists y)(\forall x) \phi(x,y) \Rightarrow (\forall x)(\exists y) \phi(x,y)$.

This question focuses on techniques to derive $(\forall x)(\exists y) \phi(x,y) \Rightarrow (\exists y)(\forall x) \phi(x,y)$, whenever it holds for $\phi(\cdot,\cdot)$.

Diagonalization is one such technique. I first see this use of diagonalization in the paper Relativizations of the $\mathcal{P} \overset{?}{=} \mathcal{NP}$ Question (see also the short note by Katz). In that paper, the authors first prove that:

For any deterministic, polynomial-time oracle machine M, there exists a language B such that $L_B \ne L(M^B)$.

They then reverse the order of the quantifiers (using diagonalization), to prove that:

There exists a language B such that for all deterministic, poly-time M we have $L_B \ne L(M^B)$.

This technique is used in other papers, such as [CGH] and [AH].

I found another technique in the proof of Theorem 6.3 of [IR]. It uses a combination of measure theory and pigeon-hole principle to reverse the order of quantifiers.

I want to know what other techniques are used in computer science, to reverse the order of universal and existential quantifiers?

Answer 1

Reversal of quantifiers is an important property that is often behind well known theorems.

For example, in analysis the difference between $\forall \epsilon > 0 . \forall x . \exists \delta > 0$ and $\forall \epsilon > 0 . \exists \delta > 0 . \forall x$ is the difference between pointwise and uniform continuity. A well known theorem says that every pointwise continuous map is uniformly continuous, provided the domain is nice, i.e., compact.

In fact, compactness is at the heart of quantifier reversal. Consider two datatypes $X$ and $Y$ of which $X$ is overt and $Y$ is compact (see below for explanation of these terms), and let $\phi(x,y)$ be a semidecidable relation between $X$ and $Y$. The statement $\forall y : Y . \exists x : X . \phi(x,y)$ can be read as follows: every point $y$ in $Y$ is covered by some $U_x = \lbrace z : Y \mid \phi(x,z) \rbrace$. Since the sets $U_x$ are "computably open" (semidecidable) and $Y$ is compact there exists a finite subcover. We have proved that $$\forall y : Y . \exists x : X . \phi(x,y)$$ implies $$\exists x_1, \ldots, x_n : X . \forall y : Y . \phi(x_1,y) \lor \cdots \lor \phi(x_n, y).$$ Often we can reduce the existence of the finite list $x_1, \ldots, x_n$ to a single $x$. For example, if $X$ is linearly ordered and $\phi$ is monotone in $x$ with respect to the order then we can take $x$ to be the largest one of $x_1, \ldots, x_n$.

To see how this principle is applied in a familiar case, let us look at the statement that $f : [0,1] \to \mathbb{R}$ is a continuous function. We keep $\epsilon > 0$ as a free variable in order not to get confused about an outer universal quantifier: $$\forall x \in [0,1] . \exists \delta > 0 . \forall y \in [x - \delta, x + \delta] . |f(y) - f(x)| < \epsilon.$$ Because $[x - \delta, x + \delta]$ is compact and comparison of reals is semidecidable, the statement $\phi(x, \delta) \equiv \forall y \in [x - \delta, x + \delta] . |f(y) - f(x)| < \epsilon$ is semidecidable. The positive reals are overt and $[0,1]$ is compact, so we can apply the principle: $$\exists \delta_1, \delta_2, \ldots, \delta_n > 0 . \forall x \in [0,1] . \phi(\delta_1, x) \lor \cdots \phi(\delta_n, x).$$ Since $\phi(\delta, x)$ is antimonotone in $\delta$ the smallest one of $\delta_1, \ldots, \delta_n$ does the job already, so we just need one $\delta$: $$\exists \delta > 0 . \forall x \in [0,1] . \forall y \in [x - \delta, x + \delta] . |f(y) - f(x)| < \epsilon.$$ What we have got is uniform continuity of $f$.

Vaguely speaking, a datatype is compact if it has a computable universal quantifier and overt if it has a computable existential quantifier. The (non-negative) integers $\mathbb{N}$ are overt because in order to semidecide whether $\exists n \in \mathbb{N} . \phi(n)$, with $\phi(n)$ semidecidable, we perform the paralel search by dovetailing. The Cantor space $2^\mathbb{N}$ is compact and overt, as explained by Paul Taylor's Abstract Stone Duality and Martin Escardo's "Synthetic Topology of Datatypes and Classical Spaces" (also see the related notion of searchable spaces).

Let us apply the principle to the example you mentioned. We view a language as a map from (finite) words over a fixed alphabet to boolean values. Since finite words are in computable bijective correspondence with integers we may view a language as a map from integers to boolean values. That is, the datatype of all languages is, up to computable isomorphism, precisely the Cantor space nat -> bool, or in mathematical notation $2^\mathbb{N}$, which is compact. A polynomial-time Turing machine is described by its program, which is a finite string, thus the space of all (representations of) Turing machines can be taken to be nat or $\mathbb{N}$, which is overt.

Given a Turing machine $M$ and a language $c$, the statement $\mathsf{rejects}(M,c)$ which says "language $c$ is rejected by $M$" is semidecidable because it is in fact decidable: just run $M$ with input $c$ and see what it does. The conditions for our principle are satisfied! The statement "every oracle machine $M$ has a language $b$ such that $b$ is not accepted by $M^b$" is written symbolically as $$\forall M : \mathbb{N} . \exists b : 2^\mathbb{N} . \mathsf{rejects}(M^b,b).$$ After inversion of quantifiers we get $$\exists b_1, \ldots, b_n : 2^\mathbb{N} . \forall M : \mathbb{N} . \mathsf{rejects}(M^{b_1}, b_1) \lor \cdots \lor \mathsf{rejects}(M^{b_n},b_n).$$ Ok, so we are down to finitely many languages. Can we combine them into a single one? I will leave that as an exercise (for myself and you!).

You might also be interested in the slightly more general question of how to transform $\forall x . \exists y . \phi(x,y)$ to an equivalent statement of the form $\exists u . \forall v . \psi(u,v)$, or vice versa. There are several ways of doing this, for example:

• Skolem normal form,
• Herbrand normal form,
• Gödel's functional interpretation.

Answer 2

Impagliazzo's hard-core set lemma allows you to switch quantifiers in the context of computational-hardness assumptions. Here's the original paper. You can find tons of related papers and posts by Googling.

The lemma says that if for every algorithm A there exists a large set of inputs on which A fails to compute a fixed function f, then in fact there exists a large set of inputs on which every algorithm fails to compute f with probability close to 1/2.

This lemma can be proved using the min-max theorem or boosting (a technique from computational learning theory), both of which are examples of switching quantifiers.

Answer 3

To me, the "canonical" proof of the Karp-Lipton theorem (that $NP \subseteq P/poly \Longrightarrow \Pi_2 P = \Sigma_2 P$) has this flavor. But here it is not the actual theorem statement in which quantifiers get reversed, but rather the "quantifiers" get reversed within the model of alternating computation, using the assumption that $NP$ has small circuits.

You want to simulate a computation of the form

$(\forall y)(\exists z)R(x,y,z)$

where $R$ is a polynomial-time predicate. You can do this by guessing a small circuit $C$ for (say) satisfiability, modifying $C$ so that it checks itself and produces a satisfying assignment when its input is satisfiable. Then for all $y$, create a SAT instance $S(x,y)$ that's equivalent to $(\exists z)R(x,y,z)$ and solve it. So you've produced an equivalent computation of the form

$(\exists C)(\forall y)[S(x,y)$ is satisfiable according to $C]$.

Answer 4

The basic use of union bound in the probabilistic method can be interpreted as a way to reverse the order of quantifiers. Although this is already mentioned in the question implicitly because the proof by Impagliazzo and Rudich is an example of this, I think that it is worth stating more explicitly.

Suppose that X is finite and that for every x∈X, we know not only that some y∈Y satisfies φ(x,y) but also that many choices of y∈Y satisfy φ(x,y). Formally, suppose that we know (∀x∈X) Pr_y∈Y [￢φ(x,y)] < 1/|X| for some probabilistic measure on Y. Then union bound allows us to conclude Pr_y∈Y [(∃x∈X) ￢φ(x,y)] < 1, which is equivalent to (∃y∈Y) (∀x∈X) φ(x,y).

There are variations of this argument:

1. If X is infinite, we can sometimes discretize X by considering a suitable metric on X and an ε-net of it. After discretizing X, we can use union bound as above.

2. When the events φ(x,y) for different values of x are almost independent, we can use the Lovász local lemma instead of union bound.

Answer 5

I'd like to add several other techniques. Although the first two techniques are not exactly for reversing the order of universal and existential quantifiers, they have a very similar flavor. Therefore, I took the opportunity to describe them here:

Averaging Lemma: Used to prove $BPP \subset P/poly$ and many other interesting theorems. Informally, assume that $S$ denotes the set of subscribers to some library, $B$ denotes the set of books in the library, and for $s\in S$ and $b \in B$, the proposition $\phi(s,b)$ is true iff "subscriber $s$ likes the book $b$." The averaging lemma states that: if for every $s \in S$, there exists at least 2/3 of $b$'s in $B$ such that $\phi(s,b)$ holds, then there exists a single $b \in B$, such that for at least 2/3 of $s$'s in $S$, the proposition $\phi(s,b)$ holds. (This can be easily proven via reductio ad absurdum and a counting argument.)

Now let $L \in BPP$, and let $M(\cdot)$ be a PPT machine which decides $L$. Suppose that the running time of $M$ is bounded by a polynomial $q(\cdot)$. Then, for any $x \in \{0,1\}^*$, and for at least 2/3 of $r$'s, $r \in \{0,1\}^{q(|x|)}$, it holds that $M_r(x) = \chi_L(x)$. Here, $M_r(\cdot)$ is the machine $M$ which uses randomness $r$, and $\chi_L(\cdot)$ is the characteristic function of $L$. The averaging lemma is then used to show that for any $n \in \mathbb{N}$, there exists a single $r \in \{0,1\}^{q(n)}$, such that for at least 2/3 of $x$'s of length $n$, $M_r(x) = \chi_L(x)$. This single $r$ works as an advice to $M$, and therefore $BPP \subset P/poly$.

NOTE: I re-emphasize that this is not a quantifier switching technique, but it has the same spirit.

Swapping Lemma: Zachos and Fürer introduced a new probabilistic quantifier $\exists^+$ (which roughly means "for most"). They proved that (omitting details):

$(\forall y)(\exists^+z) \phi(x,y,z) \Rightarrow (\exists^+ \mathbf{C})(\forall y)(\exists z \in \mathbf{C})\phi(x,y,z)$

Note that this is a second-order logic theorem.

Using the swapping lemma, they proved a number of interesting theorems, such as the BPP-theorem and Babai's $MA \subseteq AM$ theorem. I refer you to the original paper for more information.

A theorem similar to Karp-Lipton theorem mentioned in Ryan Williams post: $coNP \subset NP/Poly \Longrightarrow \Pi_3 P = \Sigma_3 P$.