alt Hacker NewsThis 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.
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.
Yes, but logic gates with constant fan-in, crucially, otherwise that's called AC.