Gibt es Parallelalgorithmen für nicht berechenbare oder unentscheidbare Probleme? Die Antwort lautet "nein". Denn jeder Parallelalgorithmus kann durch einen sequentiellen simuliert werden, durch einen einzelnen Prozessor, der sozusagen herumrennt und jedermanns Arbeit nach und nach tut.

Einer der Zwecke, für die man Parallelität eingeführt hat, liegt darin, die Laufzeit zu verringern, und zwar nach Möglichkeit drastisch. Oft wollen wir sublineare Algorithmen, welche die Parallelität in einem solchen Maße ausnutzen, daß normale Rechner in dieser Zeit nicht einmal die gesamte Eingabe lesen könnten. Diese Herausforderung führt auf die interessante Problemklasse NC. Probleme in NC gestatten äußerst schnelle Parallellösungen, viel schneller als Linearzeit (nämlich polylogarithmische Zeit), aber brauchen nur polynomial viele Prozessoren.