*non-uniform* $ACC^0$ and above classes

Problem Detail: 

$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 ACC⁰. While in some circumstances non-uniformity can be removed, this one doesn't seem to be one of them, though you never know...

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51314

3200 people like this

 Download Related Notes/Documents