$PP$ is shown to have no fixed-poly size circuit by Vinodchandran.

Bounded inside the polynomial hierarchy, $\Sigma^2_p$ is also shown to possess no fixed-poly size circuit by Kannan.

In notation, we can write $$ PP\nsubseteq SIZE(n^k)\\ \Sigma^2_p\nsubseteq SIZE(n^k) $$ for all $k$.

Has there been any improvement on these results recently?

We do not take into account non-uniform class like $MA/1$.


Your Answer

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