logoalt Hacker News

gignicoyesterday at 2:22 PM2 repliesview on HN

Yes, but logic gates with constant fan-in, crucially, otherwise that's called AC.


Replies

amlutoyesterday at 3:36 PM

I never studied these specific classes, but my immediate intuition is that an n-input fan-in AND or OR gate can be reduced to a tree of 2-input gates with depth O(log(n)), which preserves polylog complexity, so surely AC = NC.

Wikipedia agrees :)

If you specify the exponent of the log, you get a different answer.

show 1 reply
amirhirschyesterday at 2:49 PM

Yes.

There is a beautiful proof of the disjunction between AC0 and NC showing parity cannot be done in AC0 using harmonic analysis of Boolean functions

show 1 reply