5 ms·

So is it a class of problems that can be parallelized well?

• adgjlsfhk1 3mo ago
  no (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 ago
    Hmm 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 ago
      It'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 ago
        Ah got it. Reread previous comment and that makes sense.
        • dragontamer 3mo ago
          Yeah 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.