nicht angemeldet
Gibt es eigentlich Algorithmen, die nicht parallelisierbar sind (für mehrere CPU/GPU Kerne)? Nach meiner Intuition wäre das z.B. der Fall, wenn der Algorithmus sich nach jedem Rechenschritt auf das jeweilige vorherige Ergebnis beziehen muss.
Bei Wikipedia steht: "Es gehört jedoch zu den offenen Fragen der theoretischen Informatik ob alle Algorithmen, welche Probleme der Klassen P oder NP entscheiden, auch parallelisierbar sind. Für viele dieser Algorithmen wurde noch kein entsprechender paralleler Algorithmus gefunden, so dass die meisten Forscher heute davon ausgehen, dass dieses nicht der Fall ist."
Kennt jemand vielleicht einen besonders anschaulichen Fall, bei dem eine Parallelisierung nicht möglich ist?