Parallel algorithm
A parallel algorithm is an algorithm which, for example , can solve or decide a problem of the complexity class NC (Nick's Class according to Nick Pippenger ) in polynomial time.
Each parallel algorithm can also be processed sequentially. Conversely, many known sequential algorithms can also be parallelized , e.g. B. some well-known sorting algorithms like Bubblesort or Quicksort . However, one of the open questions in theoretical computer science is whether all algorithms that decide which problems of classes P or NP can also be parallelized. A corresponding parallel algorithm has not yet been found for many of these algorithms, so that most researchers today assume that this is not the case. A special machine model , which is derived from the register machine, the PRAM ( Parallel Random Access Machine ) is usually used to examine parallel algorithms .