5 ms·
This is an awesome result. For those unfamiliar: NC is the class of problems which can be solved in polylogarthmic depth with polynomial number of logic gates.
by amirhirsch 3mo ago
This is an awesome result.
For those unfamiliar: NC is the class of problems which can be solved in polylogarthmic depth with polynomial number of logic gates. It is unproven if NC != P similar to P != NP.
- gignico 3mo agoYes, 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]
- osti 3mo agoSo is it a class of problems that can be parallelized well?
- adgjlsfhk1 3mo agono (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
- osti 3mo agoHmm 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?
- chowells 3mo agoIt'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".
- osti 3mo agoAh got it. Reread previous comment and that makes sense.
- dragontamer 3mo agoYeah it's more of "on a hypothetical infinitely parallel computer, you'll get a big speedup'. Which 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.