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

  • 1
    $\begingroup$ It seems you know roughly how the solution should go. Why don't you complete it yourself? Why is our help needed? $\endgroup$ – Yuval Filmus Oct 25 '15 at 6:39
  • $\begingroup$ 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)$. $\endgroup$ – Ariel Oct 25 '15 at 21:35
  • $\begingroup$ I had a concern similar to Ariel's. $\endgroup$ – Nitin Oct 26 '15 at 1:13
  • 1
    $\begingroup$ Wikipedia suggests that the proof uses diagonalization. Have you tried that? $\endgroup$ – Yuval Filmus Oct 26 '15 at 7:46

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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