Yes, but logic gates with constant fan-in, crucially, otherwise that's called AC.
replyI 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.
replyWikipedia agrees :)
If you specify the exponent of the log, you get a different answer.
Yes.
replyThere is a beautiful proof of the disjunction between AC0 and NC showing parity cannot be done in AC0 using harmonic analysis of Boolean functions
reply
https://en.wikipedia.org/wiki/Switching_lemma
replyThat paper is in the wiki refs but Hastad’s original is from 1986
So is it a class of problems that can be parallelized well?
replyno (in both directions). lots of np/exp problems paralize well and you can be in NC and parallelize really inefficiently (e.g. you can get a 10x speedup, but you need 1000000x the hardware). the better framing is that NC is the class of efficient algorithms that can be sped up near arbitrarily by parallelization
replyHmm your last sentence seems to exactly agree that it's a class of algos that parallelize well? What does sped up arbitrarily mean? It's still polynomial speed up right?
replyIt's a difference of degree. People expect something that "parallelizes well" to show near 1-to-1 speedup. Double the hardware, double the speed. This is "you can always speed it up, but the hardware requirements can increase at any polynomial rate".
replyAh got it. Reread previous comment and that makes sense.
replyYeah it's more of "on a hypothetical infinitely parallel computer, you'll get a big speedup'.
replyWhich is still useful if you can prove a problem is in NC. It's just not quite as strong as people make it out to be.