- NC (Komplexitätsklasse)
-
NC steht in der Informatik als Abkürzung für Nick's Class (nach Nick Pippenger), die Komplexitätsklasse der parallel effizient lösbaren Entscheidungsprobleme. Die Motivation zur Bildung und Untersuchung der Klasse NC ergibt sich daraus, Probleme zu identifizieren, die auf einem Parallelrechner in deutlich besserer Zeit als auf einer sequentiell arbeitenden Maschine bei einer vertretbar großen Zahl von Prozessoren gelöst werden können (siehe auch Parallelisierung).
Inhaltsverzeichnis
Definition
Zur Definition der Klasse NC wird ein paralleles Maschinenmodell herangezogen, die sogenannte PRAM (Parallel Random Access Machine). Dabei handelt es sich um eine Registermaschine, die um Möglichkeiten zur parallelen Verarbeitung von Befehlen erweitert wurde, anschaulich um eine beliebig große Anzahl von Prozessoren bzw. Akkumulatoren. Ein Problem gehört zur Klasse NC, wenn es mit polylogarithmischer Zeit (d. h. in O(logc n), c konstant) und mit polynomiellem Aufwand (also O(nk), k konstant) auf einer PRAM entschieden werden kann. Als Aufwand bezeichnet man dabei das Produkt aus Rechenzeit und der Anzahl der Prozessoren.
Erläuterung
Zusammengefasst und vereinfacht bedeutet dies: Man betrachtet ein Problem dann als effizient lösbar durch eine parallel arbeitende Maschine, wenn die Problemlösung in logarithmischer Zeit erfolgen kann. Zum Vergleich sei angemerkt, dass man bei sequentiell arbeitenden Maschinen ein Problem dann als effizient lösbar betrachtet, wenn die Problemlösung in polynomialer Zeit erfolgen kann.
Auf einer sequentiell arbeitenden Maschine mit nur einem Prozessor ist die Zeitkomplexität gleich der Aufwandskomplexität. Umgekehrt bezeichnet der Aufwand auf einer parallel arbeitenden Maschine gerade die Zeit, die eine sequentiell arbeitende Maschine für die Berechnung benötigt.
NC und P
Das Verhältnis zwischen NC und P ist ähnlich wie das zwischen P und NP (siehe auch P-NP-Problem). Es gilt also auf jeden Fall NC ⊆ P, es ist jedoch unklar, ob auch P ⊆ NC und somit ob NC = P gilt. Man geht im Allgemeinen davon aus, dass NC eine echte Teilmenge von P ist, also NC ⊂ P.
Damit ergibt sich ebenso, dass das Verhältnis zwischen P-vollständigen Problemen und Problemen aus NC gleich dem zwischen NP-vollständigen Problemen und Problemen aus P ist: Würde man auch nur ein einziges P-vollständiges Problem finden, das in NC liegt, so folgte daraus automatisch NC = P. Aufgrund der Vermutung NC ≠ P geht man also davon aus, dass es kein P-vollständiges Problem in NC gibt.
Weblinks
- NC. In: Complexity Zoo. (englisch)
Wikimedia Foundation.
