## What is the difference between \$SIZE(n^k)\$ and \$P/poly\$?

$$SIZE(n^k)$$ is defined as the class of problems solvable with Boolean circuits (of fan-in two) with $$O(n^k)$$ gates. While $$P/poly$$ is defined as those problems over {0,1}* which can be solved by an infinite family of polynomial-size circuits $${Cn}$$.

## Why isn’t P and P/poly trivially the same?

The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf). Now, why can’t a polynomial-sized circuit be simulated in polynomial time?