1

SIZE($n^2$) consists only of problems that can be solved by circuit families of size at most $O(n^2)$. P/poly contains problems that can be solved by circuit families of size at most $O(n^3)$, and those solved by families of size at most $O(n^4)$, and so on. In particular, P/poly = $\cup_k$ SIZE($n^k$).


1

Good Question. It looks like some kind of ripple counter. It repeats after 15 steps. Values (consider the outputs to be 8,4,2,1) as 8,4,2,9,12,6,11,5,10,13,14,15,7,3,1. Zero only for one step after reset, not repeated.


Only top voted, non community-wiki answers of a minimum length are eligible