# Question about proof of Kannan's Theorem

The wikipedia page (here) assumes the existence of some $L \in \Sigma_4 - SIZE(n^k)$. How can one show that such a language exists?

This is related to a homework question, I'd prefer some hint to the answer. Using the hierarchy theorems, we can find some language $L \in SIZE(n^{k+1})$ for which $L \not \in SIZE(n^k)$. I doubt all such languages would be in $\Sigma_4$, but maybe some of them with a special property may be?

It seems we could just as well take something in $\Sigma_3$. Could we maybe take the language $L$ decided by the smallest such circuit? So then we could make a sentence like

$x \in L \iff \exists C_n$ such that for $\forall$ circuit families $C'_n \exists x'$ so that $C_n(x) = 1$ and $(|C'_n| > |C_n|$ OR $C'_n(x') != C_n(x'))$?

But it seems like this choice depends on $|x|$.

• It seems you know roughly how the solution should go. Why don't you complete it yourself? Why is our help needed? – Yuval Filmus Oct 25 '15 at 6:39
• I'm a bit confused and would like to join op question. How do you overcome the different quantification for each string $x\in \{0,1\}^n$? since you demand a different circuit in $SIZE(n^{k+1})\setminus SIZE(n^k)$ for every length $n$ string in $L$, this doesn't yield $L\notin SIZE(n^k)$. – Ariel Oct 25 '15 at 21:35
• I had a concern similar to Ariel's. – Nitin Oct 26 '15 at 1:13
• Wikipedia suggests that the proof uses diagonalization. Have you tried that? – Yuval Filmus Oct 26 '15 at 7:46

Let us denote by $C_{n,s,i}$ the i'th $n$ inputs, $s$ size circuit (relative to the lexicographic ordering of the strings describing such circuits), Then:
$x\in L \iff \exists i \hspace{1mm} \phi\left(C_{|x|,|x|^{k+1},i}\right)\forall j<i : \neg \phi\left(C_{|x|,|x|^{k+1},j}\right)\land C_{|x|,|x|^{k+1},i}(x)=1$.
$\phi(C)$ is a formula which states that $C$ cannot be computed by an $n^k$ size circuit, and can be written as a $\Pi_2$ statement (as you did in your original post).
The idea is the same as yours, trying to decide some language in $SIZE(n^{k+1})\setminus SIZE(n^k)$. The only addition is using the lexicographic ordering and forcing minimality. This way we force that for any length $n$ string, the quantification over the circuit index $i$ yields the same circuit.
After grouping the quantifiers (and moving $\forall j<i$ right after $\exists i)$ you get a $\Sigma_4$ formula.