In the Wikipedia page on the Karp–Lipton theorem it is mentioned that $$\Sigma_2\not\subseteq\mathsf{SIZE}(n^k)$$ (which is known) is not same as $$\Sigma_2\not\subseteq\mathsf{P/Poly}$$ (which is open). I was of the opinion $\mathsf{P/Poly}$ referred to polynomial size circuits which seems same as $\mathsf{SIZE}(n^k)$. Why are these circuit complexity classes different? Could someone provide an illuminating example?

Does this mean that $\mathsf{NP}\subseteq\mathsf{P/Poly}$ is possible but $\mathsf{3}$-$\mathsf{SAT}\in\mathsf{SIZE}(n)$ is impossible?

For example in this paper it is shown $\mathsf{PP}$ has linear sized circuits with respect to an oracle but not even a quantum circuit of size $\mathsf{SIZE}(n^k)$. But at $k=1$ linear circuits coincide with $\mathsf{SIZE}(n)$. Correct?

  • $\begingroup$ my understanding is that youre getting at the difference between what is known as "uniform and nonuniform" computation/ distinction which is more of an advanced topic (rarely covered at undergrad level). uniform computation is computations by TMs. unrestricted circuits of size x aka "nonuniform" may have more power than TM computations, ie, roughly, circuits of same "size" built by TMs. its a generally open question how the uniform vs nonuniform circuits are related as in your question. see circuit complexity uniformity $\endgroup$ – vzn Mar 23 '17 at 2:17
  • $\begingroup$ I fail to see what's bothering you. The paper shows that there exists some oracle, relative to which we have $\mathsf{PP}\subseteq\mathsf{SIZE}(n)$. In the non-blackbox model however, no such result is known (and is believed to be false). $\endgroup$ – Ariel Mar 23 '17 at 8:30
  • $\begingroup$ @Ariel I accepted your answer. But just was little uncertain and removed accept. I will accept your answer after confirming. Also vinodchandran has showed $\mathsf{PP}\not\subseteq\mathsf{SIZE}(n^k)$ for any fixed $k\in\Bbb N$. So how is it possible with respect to an oracle? $\endgroup$ – Bread Winner Mar 23 '17 at 8:30
  • $\begingroup$ I'm not pushing my answer to be accepted (feel free of course to wait for better answers). Just wondering what's the confusion all about $\endgroup$ – Ariel Mar 23 '17 at 8:31
  • $\begingroup$ what is non-black box model and how is black box model and oracle access related? $\endgroup$ – Bread Winner Mar 23 '17 at 8:32

$\mathsf{P/Poly} = \bigcup\limits_{k\in\mathbb{N}}\mathsf{SIZE}(n^k)$.

We don't know if every language in $\Sigma_2$ has a polynomial size circuit, but we do know that we cannot have polynomial circuits of bounded degree,i.e. $\mathsf{SIZE}(n^k)$ for some $k\in \mathbb{N}$, for all languages in $\Sigma_2$ (Kannan's theorem).

  • $\begingroup$ Does this mean that $\mathsf{NP}\subseteq\mathsf{P/Poly}$ is possible but $\mathsf{3}$-$\mathsf{SAT}\in\mathsf{SIZE}(n)$ is impossible? $\endgroup$ – Bread Winner Dec 27 '15 at 9:01
  • $\begingroup$ $NP\subseteq \mathsf{P/Poly}$ is possible (if we knew that $NP\not\subseteq \mathsf{P/Poly}$ then $\mathsf{P}\neq \mathsf{NP}$ since $\mathsf{P}\subseteq \mathsf{P/Poly}$). I am not sure what this implies regarding the possibility of having linear size circuits for 3SAT. What kannan's theorem tells you is that you cannot have linear (or any fixed degree) size circuits for all languages in $\Sigma_2$ (so there exists for example $L\in \Sigma_2$ with no linear size circuits). I think $NP\subseteq SIZE(n)$ is open. $\endgroup$ – Ariel Dec 27 '15 at 9:34

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.