Emile Timothy

Happy Monday! Today, I'm going to share something really cool about the polynomial hierarchy. I know that I've written prior entries about the polynomial hierarchy where I've praised some of its properties, but this result about the Polynomial Hierarchy is the WILDest thing ever! If you're new here, I'm going to start by giving my regular schpiel about what the polynomial hierarchy is.

Define $\Delta_0^P := \Sigma_0^P := \Pi_0^P:=P$, where $P$ is the set of problems that can be solved in poly-time. Then, for all $i \geq 0$, define: $$\Delta_{i+1}^P:=\text{P}^{\Sigma_i^P}$$ $$\Sigma_{i+1}^P:=\text{NP}^{\Sigma_i^P}$$ $$\Pi_{i+1}^P:=\text{coNP}^{\Sigma_i^P}$$ The polynomial-time hierarchy is defined as: $$\text{PH} = \bigcup_{i\in\mathbb{N}} \{\Delta_i^P, \Sigma_i^P, \Pi_i^P\}$$ The result that I want to show here is that every language in the polynomial hierarchy is equivalent in computational power to the complexity class of symmetric functions $S_2^P$, which resides between the first and second levels of the polynomial hierarchy.

The formal definition of $S_2^P$ is that any language $L$ is said to be in $S_2^P$ if there is a polynomial-time predicate $P$ such that:
If $x\in L$, then there exists a $y$ such that for all $z$, $P(x,y,z)=1$
If $x\not\in L$, then there exists a $z$ such that for all $y$, $P(x,y,z)=0$

Another, more intuitive way to look at $S_2^P$ is the following: Suppose that a polynomial-time computable judge has to decide whether a string $x$ is in a language $L$. Two lawyers submit written arguments to convince the judge, one arguing for the string in the language and the other arguing for the string to be out of the language. Neither lawyer can see the others arguments. For what languages can we have the judge always convinced? (The answer is $S_2^P$!)

Let L be an arbitrary language in $𝑆_𝑝$. It follows by definition then that: $$ 𝑥 ∈ 𝐿 ⇒ ∃𝑦 ∀𝑧, (𝑥, 𝑦, 𝑧) ∈ 𝑅$$ $$ 𝑥 ∉ 𝐿 ⇒ ∃𝑧 ∀𝑦, (𝑥, 𝑦, 𝑧) ∉ 𝑅 $$ However, note that the order of the universal and existential quantifiers is commutative in this case only if the commutator is taken in both directions. So, from this we can write two alternate versions of the definition, where version 1 commutes the quantifiers in the case for $𝑥 ∈ 𝐿$ while holding the case for $𝑥 ∉ 𝐿$ to be constant, and version 2 commutes the quantifiers in the case for $𝑥 ∉ 𝐿$ while holding the case for $𝑥 ∈ 𝐿$ to be constant. This procedure yields:

Version 1: $$𝑥 ∈ 𝐿 ⇒ ∀𝑧 ∃𝑦, (𝑥, 𝑦, 𝑧) ∈ 𝑅$$ $$𝑥 ∉ 𝐿 ⇒ ∃𝑧 ∀𝑦, (𝑥, 𝑦, 𝑧) ∉ 𝑅$$ Version 2: $$𝑥 ∈ 𝐿 ⇒ ∃𝑦 ∀𝑧, (𝑥, 𝑦, 𝑧) ∈ 𝑅$$ $$𝑥 ∉ 𝐿 ⇒ ∀𝑦 ∃𝑧, (𝑥, 𝑦, 𝑧) ∉ 𝑅$$ However, by definition, the complexity class that version 1 decides is equal to $\Sigma_2^P$, and the complexity class that version 2 decides is equal to $\Pi_2^P$. Therefore, if $𝑥 ∈ S_2^P$ then $𝑥 ∈ \Sigma_2^P$ and $𝑥 ∈ \Pi_2^P$.

Therefore, we have that: $$S_2^𝑃 ⊆ (\sigma_2^P ∩ \Pi_2^P)$$ QED.

The language LEX-FIRST-ACCEPTANCE consists of those pairs $(𝑪_𝟏, 𝑪_𝟐)$ for which $𝑪_𝟏, 𝑪_𝟐$ are circuits, and the lexicographically first-string $x$ for which $𝑪_𝟏(𝒙) = 𝟏$ is also accepted by $𝑪_𝟐$. (If there is no lexicographically first string, i.e., $𝑪_𝟏$ is unsatisfiable, then $(𝑪_𝟏, 𝑪_𝟐)$ is not in the language). A bitstring $x$ lexicographically precedes a bitstring $y$ if the first position $i$ in which they differ has $𝒙_𝒊 = 𝟎$ and $𝒚_𝒊 = 𝟏$.

The purpose of this lemma is to show that LEX-FIRST-ACCEPTANCE is $P^{\text{NP}}$-complete - that not only is it solvable by $P^{\text{NP}}$ Turing Machine, but also it is representative of every problem in the $P^{\text{NP}}$ complexity class.

Sub-Lemma 2.1: $𝐿𝐹𝐴 ∈ P^{\text{NP}}$:

Given an instance $(𝐶_1, 𝐶_2)$, call the $\text{NP}$ oracle to determine the first lexicographically first string $𝑥 ∈ \{0, 1\}^𝑛$ that is accepted by $𝐶_1$. The $\text{NP}$ oracle nondeterministically evaluates each string with $𝐶_1$ but uses an arbitrary enumeration scheme to prioritize which string that is accepted by $𝐶_1$ is lexicographically first. If there is no such string, the machine returns false.

If $∃$ a lexicographically-first string $x$, the $P$ machine would check if $𝐶_2(𝑥) = 1$:

If $𝐶_2(𝑥) = 1$, the $P$ machine returns ACCEPT.

If $𝐶_2(𝑥) = 0$, the $P$ machine returns REJECT.

QED.

In Lemma 2, I showed that LEX−FIRST−ACCEPTANCE (LFA) $∈ \text{P}^\text{NP}$-complete. Therefore, to show that $P^\text{NP} ⊆ 𝑆_2^P$, we can instead just show that $\text{LFA} ∈ S_2^P$ since $\text{LFA}$ can then be generalized to all other languages in $𝑃^{\text{NP}}$. Therefore, our goal is to show that for some predicate $T$:
$$1) ∀𝑥∈\text{LFA}, ∃𝑦∀𝑧, 𝑇(𝑥,𝑦,𝑧)=1$$ $$2) ∀𝑥∉\text{LFA}, ∃𝑧∀𝑦, 𝑇(𝑥,𝑦,𝑧)=0$$ Given an instance $(𝐶_1, 𝐶_2)$ of $\text{LFA}$, we let $𝜙(𝑥, 𝑦)$ be the lexicographically-first string (to be accepted by circuit $𝐶_1$) between $x$ and $y$. Therefore, we define the following predicate $T$: $𝑇(𝑥, 𝑦, 𝑧) = 𝐶_2(𝜙(𝑥, 𝑦))$.

In the case that $𝐶_1(𝑥)$ and $𝐶_1(𝑦)$ are both $0$, there is no lexicographically-first string. In this case, we simply set $𝑇(𝑥, 𝑦, 𝑧) = 0$. However, we can rewrite this as: $$(𝐶_1,𝐶_2) ∈ \text{LFA} \Rightarrow ∃y∀z(∀x), T(x,y,z) = 1 \Rightarrow ∃y∀x, T(x,y)=1$$ $$(𝐶_1,𝐶_2) ∉ \text{LFA} \Rightarrow ∃z∀y(∀x), T(x,y,z) = 0 \Rightarrow ∃x∀y, T(x,y)=0$$ Since this is the definition of $𝑆_2^𝑃$ (modified from above), this implies that $\text{LFA} ∈ 𝑆_2^𝑃$. Hence, by the $\text{P}^{\text{NP}}$-completeness of $\text{LFA}$, we have that: $$\text{P}^{\text{NP}} ⊆ 𝑆_2^P$$ QED.

$∀ 𝐿_1 ∈ \text{MA}$, we have by definition that: $$𝑥 ∈ 𝐿_1 ⇒ ∃𝑦, \Pr\limits_z [(𝑥,𝑦,𝑧)∈𝑅]≥\frac{2}{3}$$ $$𝑥 ∉ 𝐿_1 ⇒ ∀𝑦, \Pr\limits_z [(𝑥,𝑦,𝑧)∈𝑅]≤\frac{1}{3}$$ $∀ 𝐿_2 ∈ 𝑆_2^P$, we have by definition that: $$𝑥 ∈ 𝐿_2 ⇒ ∃𝑦∀𝑧, (𝑥,𝑦,𝑧)∈𝑅$$ $$𝑥 ∉ 𝐿_2 ⇒ ∃𝑧 ∀𝑦, (𝑥,𝑦,𝑧)∉𝑅$$ We can increase the probability of successfully accepting a “yes” instance through error reduction, from which we know that $∀ 𝐿_1 ∈ \text{MA}, ∃𝑅 ∈ P$ such that: $$𝑥 ∈ 𝐿_1 ⇒ ∃𝑦, \Pr\limits_z[(𝑥,𝑦,𝑧)∈𝑅]=1$$ $$𝑥 ∉ 𝐿_1 ⇒ ∀𝑦, \Pr\limits_z[(𝑥,𝑦,𝑧)∈𝑅]≤\frac{1}{3}$$ Similarly, we can successfully decrease the probability of incorrectly accepting a “no” instance through repeated error reduction which reduces the probability to: $$𝑥 ∈ 𝐿_1 ⇒ ∃𝑦, \Pr\limits_z[(𝑥,𝑦,𝑧)∈𝑅]=1$$ $$𝑥 ∉ 𝐿_1 ⇒ ∀𝑦, \Pr\limits_z[(𝑥,𝑦,𝑧)∈𝑅]≤ \frac{1}{2^{|𝑦|}}$$ We claim then through these definitions that $∀𝐿 ∈ \text{MA}, 𝐿 ∈ 𝑆_2^P$. To show that $𝑥 ∈ 𝐿 ⇒ ∃𝑦, \Pr\limits_z[(𝑥, 𝑦, 𝑧) ∈ 𝑅] = 1$ is contained in $𝑥 ∈ 𝐿_2 ⇒ ∃𝑦 ∀𝑧, (𝑥, 𝑦, 𝑧) ∈ 𝑅$: Since the probability of $(𝑥, 𝑦, 𝑧) ∈ R$ is $1$ for all $z$: $$𝑥 ∈ 𝐿_1 ⇒ ∃𝑦, \Pr\limits_z [(𝑥,𝑦,𝑧)∈𝑅]=1$$ $$ ⇒ 𝑥 ∈ 𝐿_2 ⇒ ∃𝑦 ∀𝑧, (𝑥,𝑦,𝑧)∈𝑅$$ Using Boole’s inequality, we can take the union bound of the probability of incorrectly accepting a “no” instance of $L$ across all possible values of $y$ to get: $$𝑥 ∉ 𝐿_1 ⇒ ∀𝑦, \Pr\limits_z [(𝑥,𝑦,𝑧)∈𝑅]≤ \frac{1}{2^{|y|}}$$ $$∈ ∃𝑦 \text{ such that }\Pr\limits_z [(x, y, z)∈𝑅] ≤ \frac{1}{2^{|y|}}\times 2^{|y|}$$ $$= ∃𝑦 \text{ such that }\Pr\limits_z [(x, y, z)∈𝑅] =1$$ $$∈ ∃ 𝑧 \text{ such that } ∀y(x, y, z)∉𝑅$$ $$𝑥 ∉ L_2 ⇒ ∃𝑧 ∀y, (x, y, z) ∉ 𝑅$$ These equations fits the necessary condition for all languages in $𝑆_2^P$. Therefore, we have that: $$∀ 𝐿 ∈ \text{MA}, \text{MA} ∈ 𝑆_2^P$$ $$\text{MA} ⊆ 𝑆_2^P$$ QED.

Lemma $1$: $\text{BPP} ⊆ \text{MA}$

Given an arbitrary language $\text{L} \in \text{BPP}$, we can show that there is an $\text{MA}$ protocol that decides an instance $x$:

Merlin (the prover) sends a single TRUE ($1$) bit (This is just a filler so that Merlin is doing something)

Arthur (the verifier) disregards Merlin’s bit and simulates the $\text{BPP}$ machine for $L$ on $x$.

Note here that this is only possible since Arthur has the ability to flip coins and make random decisions.

If the $\text{BPP}$ machine returns “TRUE”, Arthur returns “TRUE”.

If the BPP machine returns “FALSE”, Arthur returns “FALSE”.

Completeness and Soundness are intact here because Arthur simulates the $\text{BPP}$ machine which has the same probabilities:

In particular, $∀𝑥 ∈ L$, $\Pr[𝑥 \text{ accepted}] ≥ \frac{2}{3}$ and $∀𝑥 ∉ L$, $\Pr[𝑥 \text{ rejected}] ≥ \frac{2}{3}$.

Therefore, any language in $\text{BPP}$ has an $\text{MA}$ protocol that decides it. Hence, $\text{BPP} ⊆ \text{MA}$.

QED.

Therefore, since we know that $\text{BPP} ⊆ \text{MA}$, we can use the transitivity property and the result proven in Lemma 4 to obtain:
$$\text{BPP} ⊆ \text{MA} ⊆ S_2^P$$ From this, we have that $\text{BPP} ⊆ S_2^P$.

QED.

It is known from the Cook-Levin theorem that $\text{SAT} ∈ \text{NP-complete}$. Therefore, if $\text{SAT}$ has polynomial-size circuits, then: $$ \text{NP} \subseteq \text{P}/\text{poly}$$ To show that $\text{PH} = S_2^P$, we need to show that:
1) $\text{PH} = \Sigma_2^P$
2) $\text{PH} = \Pi_2^P$

In Lemma $1$, we showed that $\text{PH} \subseteq \Sigma_2^P \cap \Pi_2^P$. Therefore, the onus of this proof is to show that:
1) $\Sigma_2^P ⊆ \text{PH}$
2) $\Pi_2^P ⊆ \text{PH}$

Sub-Lemma 6.1: $\Sigma_2^𝑃 = \text{PH}$

This follows from the regular Karp-Lipton theorem shown in Lemma 4.

Therefore, $\Sigma_2^𝑃 ⊆ \text{PH}$ is trivially true.

QED.

Sub-Lemma 6.2: $\Pi_2^P ⊆ \text{PH}$:

Let $𝐶$ be a family of circuits which output $1$ on satisfiable inputs and $0$ on unsatisfiable inputs.

Let $C'$ be the family of circuits using self-reducibility of $\text{SAT}$ instances to output satisfying assignments for $\text{SAT}$ formulas.

Let $L$ be an arbitrary language in $\Pi_2^P$ and let $𝜙$ be a predicate in $P$. It follows then that:

$$𝑥∈𝐿 ⇒ ∀𝑦∃𝑧, 𝜙(𝑥,𝑦,𝑧)=1$$ $$𝑥∉𝐿 ⇒ ∃𝑦∀𝑧, 𝜙(𝑥,𝑦,𝑧)=0$$

However, note here that $\{(𝑥, 𝑦) | ∃𝑧, φ(x, y, z) = 1\}$ is by definition in $\text{NP}$ (where $z$ is a witness).

Therefore, $C'$ must exist to find satisfying assignments $z$ for satisfying formulas $x$.

We define the predicate $𝜙'$ to be the polynomially verifiable instance $(𝐶, 𝑥, 𝑦)$.

Note that $(C,x,y)$ is $\text{TRUE}$ if $𝐶'(𝑥) = 𝑧$, where $𝜙(𝑥, 𝑦, 𝑧) = 1$, and $\text{FALSE}$ otherwise.

Therefore,

$$𝑥∈𝐿⇒ ∃𝐶 \text{ such that }∀𝑦, 𝐶'(𝑥)=𝑧 \text{ such that } 𝜙'(𝑥,𝑦,𝑧)=1$$ $$𝑥∉𝐿⇒ ∀𝐶 \text{ such that }∃𝑦 ∀𝑧, 𝐶'(𝑥)=𝑧 \text{ such that } 𝜙'(𝑥,𝑦,𝑧)=0$$

However, this can just be rewritten as:

$$𝑥∈𝐿 ⇒ ∃𝐶∀𝑦, 𝜙'(𝐶,𝑥,𝑦)=1$$ $$𝑥∉𝐿 ⇒ ∃𝑦∀𝐶, 𝜙'(𝐶,𝑥,𝑦)=0$$

Therefore, by definition $𝐿 ∈ S_2^𝑃$. Since $L ∈ \Pi_2^P$, we have that $\Pi_2^P ⊆ S_2^P$.

QED.

Therefore, since we have shown that $$\Sigma_2^P ⊆ \text{PH},\quad \Pi_2^P ⊆ \text{PH},$$ and since we already know that $$\text{PH} ⊆ \Sigma_2^𝑃 ∩ \Pi_2^P,$$ we now have that $$\text{PH} = \Sigma_2^P \text{ and } \text{PH} = \Pi_2^𝑃.$$ Therefore, $$S_2^P = \Pi_2^P = \Sigma_2^P.$$ This gives us: $$\text{PH} = S_2^P$$ QED.

Blog