World's most popular travel blog for travel bloggers.

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

, , No Comments
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 ACC0. 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 :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback