0
$\begingroup$

$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$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\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$
    – Turbo
    Commented Dec 31, 2015 at 22:59
  • $\begingroup$ That's definitely false. Non-uniform ACC^0 contains uncomputable functions. $\endgroup$
    – Yuval Filmus
    Commented Dec 31, 2015 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$
    – Turbo
    Commented Dec 31, 2015 at 23:02
  • 1
    $\begingroup$ I don't know, I'm not a complexity oracle. $\endgroup$
    – Yuval Filmus
    Commented Dec 31, 2015 at 23:03
  • 1
    $\begingroup$ It should be. I don't remember said circumstances. I could also be wrong. $\endgroup$
    – Yuval Filmus
    Commented Dec 31, 2015 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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