[Solved]: Question about proof of Kannan's Theorem

Problem Detail: 

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

Asked By : Nitin

Answered By : Ariel

Following your way:

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48693

3.2K people like this

 Download Related Notes/Documents