Parallel algorithm

A parallel algorithm is an algorithm which, for example, a problem of complexity class NC (Nick's class after Nick Pippenger ) solve in polynomial time and decide. Each parallel algorithm can also be processed sequentially. Many well-known sequential algorithms Conversely parallelizable, for example, some well-known sorting algorithms such as bubble-sort or quicksort. However, it is one of the open questions in theoretical computer science that all algorithms decide which problems of the classes P and NP, are also parallelizable. For many of these algorithms yet no corresponding parallel algorithm has been found, so most researchers today assume that this is not the case. To investigate parallel algorithms are used usually a special machine model that is derived from the register machine, the PRAM (Parallel Random Access Machine).