0
$\begingroup$

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

For reference:

  • $\text{SIZE}(n^k)$ is defined as the class of problems solvable with Boolean circuits (of fan-in two) with $O(n^k)$ gates.

  • $\text{P}/\text{poly}$ is defined as those problems over $\{0,1\}^*$ which can be solved by an infinite family of polynomial-size circuits ${C_n}$.

What is the difference between these classes?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy