[Solved]: Simple lower bounds against AC0

Problem Detail: 

It is known that $Parity \notin AC^0$ (nonuniform), but the proof is rather involved and combinatorial. Are there simpler, but weaker lower bounds, say for $NP \not \subseteq AC^0$ or $NEXP \not \subseteq AC^0$?

For example, can nontrivial simplifications be obtained in the proof of $NEXP \not \subseteq ACC^0$ to deal only with the special case of $AC^0$?

Asked By : sdcvvc

Answered By : Ryan Williams

I guess it depends on your point of view, but the proof via approximating polynomials (along the lines of Razborov-Smolensky) that Parity isn't in AC0 is not so involved...

The natural way in which one would modify the proof that "NEXP is not in ACC0" to yield "NEXP not in AC0" would be to give a SAT algorithm for AC0 circuits that beats exhaustive search. However, all known SAT algorithms of this kind actually use the same or similar techniques as the "Parity not in AC0" lower bounds, so the proof would not get any simpler. (It would be interesting to find an AC0 SAT algorithm where this is not the case.)

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents