gotchaMinor
Difference between $\mathsf{SIZE}(n^k)$ vs $\mathsf{P/poly}$ and $\mathsf{SIZE}(n)$ vs linear size circuit?
Viewed 0 times
mathsflinearsizedifferencebetweenpolyandcircuit
Problem
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?
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?
Solution
$\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).
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).
Context
StackExchange Computer Science Q#51174, answer score: 6
Revisions (0)
No revisions yet.