3 ms·
Yes, but logic gates with constant fan-in, crucially, otherwise that's called AC.
by gignico 3mo ago
Yes, but logic gates with constant fan-in, crucially, otherwise that's called AC.
- amirhirsch 3mo agoYes. 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
- ZeroCool2u 3mo agoThis one? https://www.cs.huji.ac.il/~nati/PAPERS/lmn.pdf https://www.cs.huji.ac.il/~nati/PAPERS/lmn.pdf
- amirhirsch 3mo agohttps://en.wikipedia.org/wiki/Switching_lemma https://en.wikipedia.org/wiki/Switching_lemma That paper is in the wiki refs but Hastad’s original is from 1986
- amluto 3mo agoI 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.
- fleahunter 3mo ago[flagged]