« first day (1841 days earlier)   

10:36 AM
1
Q: Difference between $\mathsf{SIZE}(n^k)$ vs $\mathsf{P/poly}$ and $\mathsf{SIZE}(n)$ vs linear size circuit?

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

 

« first day (1841 days earlier)