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?

  • 13
    Wow, this is a great question. Just reading it made me look at "familiar" objects differently. Thanks! – Mark Reitblatt Jan 22 '11 at 2:17
up vote 68 down vote accepted

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:

  • 4
    It is a very general condition (one space must be overt, the other compact, and the relation open), but it is also a technique: if you can find topologies that satisfy the conditions then you can invert the quantifiers. – Andrej Bauer Jan 22 '11 at 13:08
  • 7
    @Andrej, your answer is really good and educational. I never knew there's a relation between compactness and reversing quantifiers, until this post appears. I feel enlightened. – Hsien-Chih Chang 張顯之 Jan 22 '11 at 16:28
  • 7
    What an amazing answer. – Suresh Venkat Jan 22 '11 at 17:14
  • 10
    I feel flattered. I wish more people knew about the intimate connections between logic, computation and topology. – Andrej Bauer Jan 22 '11 at 17:21
  • 6
    @Andrej: Is there a good reference (specially a book or a lecture note) on the "intimate connections between logic, computation and topology"? – M.S. Dousti Jan 22 '11 at 19:55

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.

  • 3
    That's an excellent point. – Suresh Venkat Jan 22 '11 at 17:16

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]$.

  • Outstanding! This is an example of assumption-based quantifier switching. – M.S. Dousti Jan 22 '11 at 19:43
  • Although this is perfectly correct, I wanted to suggest writing $NP \subset P/poly$ instead of $NP \subseteq P/poly$, since NP can never equal P/poly. – M.S. Dousti Jan 23 '11 at 10:18

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 xX, we know not only that some yY satisfies φ(x,y) but also that many choices of yY satisfy φ(x,y). Formally, suppose that we know (∀xX) PryY [¬φ(x,y)] < 1/|X| for some probabilistic measure on Y. Then union bound allows us to conclude PryY [(∃xX) ¬φ(x,y)] < 1, which is equivalent to (∃yY) (∀xX) φ(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.

  • 2
    Tsuyoshi, this is terribly off topic, but it's time to nominate yourself as a moderator :) – Suresh Venkat Jan 25 '11 at 0:39

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$.

  • Nitpicking: I would like to note that the actual proof of BPP⊆P/poly requires a little more than what is written here, because an advice string which works only for 2/3 fraction of instances is insufficient. But I think that the important point of the first half of this answer is that the proof of BPP⊆P/poly can be viewed as something similar to quantifier reversal, which is perfectly valid. – Tsuyoshi Ito Jan 25 '11 at 20:58
  • @Tsuyoshi: You are right. But the rest of proof uses the sequential repetition and Chernoff bound, to prove the existence of an $r$ which works for all but an exponentially small fraction of inputs; and as you said, that does not have to do with quantifier reversal, so I omitted it. – M.S. Dousti Jan 25 '11 at 23:30
  • I am not sure if you got my point. My point is that the statement of the “averaging lemma” is not sufficient to prove BPP⊆P/poly. You need a slightly finer estimate, namely the estimate of the expected probability E_b [Pr_s φ(s,b)] instead of max_b [Pr_s φ(s,b)]. – Tsuyoshi Ito Jan 26 '11 at 1:00
  • @Tsuyoshi: I'm afraid I didn't get you. In the previous comment, I noted that we first amplify the 1/3 error to $2^{-|x|}$, and then apply the averaging lemma. Here is a full-blown proof, taken from Goldreich's book. Am I missing something? – M.S. Dousti Jan 26 '11 at 8:16
  • Thanks! I had been misunderstanding your comment. I did not know that BPP⊆P/poly can be proved by first reducing the error and then applying the averaging lemma (I was thinking of the opposite order). – Tsuyoshi Ito Jan 26 '11 at 21:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.