$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$?
Asked By : Turbo
Answered By : Yuval Filmus
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...
Question Source : http://cs.stackexchange.com/questions/51314
0 comments:
Post a Comment
Let us know your responses and feedback