$NEXP$ smallest class above $ACC^0$ that we know is separated from $ACC^0$.

We do not know if either $NP$ or $P/poly$ is in $ACC^0$.

Suppose every problem in $NP$ can be solved in polynomial time with polynomial sized advice string (that is $NP\subseteq P/poly$ holds) however the circuit that computes it needs only $ACC^0$ type structure?

Would that mean $NP$ is in non-uniform $ACC^0$ or uniform $ACC^0$?


It would imply that NP is in non-uniform ACC0. While in some circumstances non-uniformity can be removed, this one doesn't seem to be one of them, though you never know...

  • $\begingroup$ my query is simple I will ask here is non-uniform ACC^0 contained in any uniform ACC^i or at least uniform TC^i at any i>0? $\endgroup$ – Bread Winner Dec 31 '15 at 22:59
  • $\begingroup$ That's definitely false. Non-uniform ACC^0 contains uncomputable functions. $\endgroup$ – Yuval Filmus Dec 31 '15 at 23:01
  • $\begingroup$ how about non-uniform $ACC^0\cap EXPSPACE$? Is it in any uniform $ACC^i \cap EXPSPACE$ or at least uniform $TC^i\cap EXPSPACE$ at any i>0? $\endgroup$ – Bread Winner Dec 31 '15 at 23:02
  • 1
    $\begingroup$ I don't know, I'm not a complexity oracle. $\endgroup$ – Yuval Filmus Dec 31 '15 at 23:03
  • 1
    $\begingroup$ It should be. I don't remember said circumstances. I could also be wrong. $\endgroup$ – Yuval Filmus Dec 31 '15 at 23:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.