# Prove that $\Sigma_{i}\text{SAT}$ is a complete problem for $\Sigma_{i}^{p}$

I'm trying to prove that $$\Sigma_{i}\text{SAT}$$ is a complete problem for $$\Sigma_{i}^{p}$$.

Using induction on $$i$$, I can see that for the base case, when $$i=1$$, $$\Sigma_{1}\text{SAT}$$ is equivalent to $$SAT$$. Since, $$\Sigma_{1}^{p} = NP$$, then $$\Sigma_{1}\text{SAT}$$ is a complete problem for $$\Sigma_{1}^{p}$$.

Assuming that this is true for $$i-1$$, I now need to show it for $$\Sigma_{i}SAT$$. I'm thinking of showing that $$\Sigma_{i}SAT$$ is "equivalent" (not too sure here) to $$\Sigma_{i-1}SAT$$, with a fixed $$u_1, \cdots, u_{i-1}$$ (which is $$\Sigma_{i-1}^{p}$$ complete by the inductive hypothesis) and an additional quantifier $$\exists$$ or $$\forall$$.

Is this the correct way to proceed?

Thanks for the help!

I took inspiration from the proof given in "Complete sets and the Polynomial-time hierarchy" of Wrathall. However, I tried to focus mainly on the intuitions, since the original proof is pretty long. Let us focus on the induction step:

Membership:

Let $$\phi=\exists X_1 \forall X_2 \dots Q_i X_i(F(X_1, X_2, \dots, X_i))$$. We want to show that deciding if $$\phi$$ is satisfiable is a problem in $$\Sigma^p_i$$, where each $$X_j$$ contains a polynomial number of boolean variables in $$n$$, where $$n=|\phi|$$.

One can use the hypothesis induction and say that the safisfiability problem for $$\phi'=\forall X_2 \dots Q_i X_i(F(X_2, \dots, X_i))$$ belongs to $$\Pi_{i-1}^p$$. At this point is should be easy to see that one can build a ND Turing Machine with a $$\Pi_{i-1}SAT$$ oracle such that it guesses in polynomial time an assignment for the variables in $$X_1$$ ($$|X_1| \leq n$$), and check if it is satisfiable using an $$\Pi_{i-1}SAT$$ oracle call.

Hardness:

Lemma 1 (polynomial erasing). Given a language $$L$$, $$L\in \Sigma^p_i$$ $$\iff$$ $$h(L')=L$$, where $$h$$ is a polynomial erasing homomorphism (with respect to conjunction), i.e. $$|x|\leq p(|h(x)|)$$ for some polynomial $$p$$.

The ($$\impliedby$$) proof is very similar to the argument used above for the membership.

The main idea is for the ($$\implies$$) case is to see that $$L\in \Sigma^p_i \iff$$ $$\exists L_1 \in P, L_2\in \Sigma^p_{i-1}, L_3\in \Pi^p_{i-1}$$ such that $$L=h(L_1 \cap L_2 \cap L_3)$$.

Each word in $$L_j$$ for $$j=1,2,3$$ has the following format:

$$(x, y, v, z)$$ where the intuition is that

• $$x$$ is the input (the one you are testing the membership in $$L$$),
• $$y$$ is a sequence of TM operations that leads the machine to call some oracles,
• $$v$$ is a sequence of words that belong to $$L_2$$
• $$z$$ is a sequence of words that do not belong to $$L_3$$

To understand what it is going on, you can read the $$y$$ has a sequence of instructions that lead the Turing Machine to call (multiple times) oracles in $$L_2$$ and $$L_3$$.

Now, you can apply the $$h$$ function to $$(L_1 \cap L_2 \cap L_3)$$, obtaining that $$h(L_1 \cap L_2 \cap L_3)=h(L_1) \cap h(L_2) \cap h(L_3)$$

By definition, $$L1$$ (polynomial) and $$L_2$$ ($$\Pi^p_{i-1}$$), therefore they are both in the set of languages defined as {$$h'(L)$$} for some $$L\in \Pi^p_{i-1}$$ and $$h'$$ a polynomial erasing homomorphism.
By induction hypothesis, since $$L_3\in \Sigma^p_{i-1}$$, then there exists an homomorhpism $$h'$$ such that the target language is in $$\Pi_{i-2}^p$$, therefore in $$\Pi_{i-1}^p$$ as well.

Lemma 1 allows us to obtain the following Lemma:

Lemma 2 If $$L \in \Sigma^p_i$$ and $$x\in L$$ then, $$\exists y$$ s.t. $$|y|=p(|x|)$$ for some polynomial $$p$$, and $$xy\in L'$$ with $$L'\in \Pi^p_{i-1}$$.

This result can be obtained by induction by applying Lemma 1. Note that in Lemma 1 there is an inequality, while here there is an equality. The trick is to extend the alphabet with a new character which can be used as padding.

At this point, we have all the tools to conclude that $$\Sigma_iSAT$$ is complete for $$\Sigma^p_i$$. One can use the hypothesis induction:

$$\Phi=$${$$\phi=\forall X_2 \dots Q_i X_i(F(X_2, \dots, X_i)) | \phi$$ is true} is complete for $$\Pi^p_{i-1}$$, and apply Lemma 2.

Intuitively, you can encode the word $$y$$ of Lemma 2 using a polynomial number of propositional variables. For example, since we know that $$|y|=p(|x|)$$, and a finite alphabet $$\Gamma$$, we can interpret $$x_{k,l}$$ as a propositional variable which is true if and only if the k-th position of the word coincides with the l-th symbol in $$\Gamma$$. The set {$$x_{k,l}$$} will coincide with the set $$X_1$$ of the statement (see the paper of Wrathall for further details on the encoding).

In that way, you can obtain the desired result. Note that the discussion is only about $$\Sigma^p_i$$, we can refer to the induction hypothesis on $$\Pi^p_i$$ as well because they are complementary.