|
|
|
|
|
|
by amluto
36 days ago
|
|
|
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. |
|
|