5
$\begingroup$

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?

$\endgroup$
10
  • $\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, 2017 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, 2017 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$
    – Turbo
    Mar 23, 2017 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, 2017 at 8:31
  • $\begingroup$ what is non-black box model and how is black box model and oracle access related? $\endgroup$
    – Turbo
    Mar 23, 2017 at 8:32

1 Answer 1

6
$\begingroup$

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

$\endgroup$
2
  • $\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$
    – Turbo
    Dec 27, 2015 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, 2015 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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