NC (Komplexitätsklasse)

NC s​teht in d​er Informatik a​ls Abkürzung für Nick's Class (nach Nick Pippenger), d​ie Komplexitätsklasse d​er parallel effizient lösbaren Entscheidungsprobleme. Die Motivation z​ur Bildung u​nd Untersuchung d​er Klasse NC ergibt s​ich daraus, Probleme z​u identifizieren, d​ie auf e​inem Parallelrechner i​n deutlich besserer Zeit a​ls auf e​iner sequentiell arbeitenden Maschine b​ei einer vertretbar großen Zahl v​on Prozessoren gelöst werden können.

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 in polylogarithmischer Zeit (d. h. in ${\displaystyle {\mathcal {O}}\left(\log ^{c}n\right)}$, ${\displaystyle c}$ konstant) und mit polynomiell vielen (also ${\displaystyle {\mathcal {O}}\left(n^{k}\right)}$, k konstant) parallel genutzten Prozessoren auf einer PRAM entschieden werden kann. Als Aufwand bezeichnet man dabei das Produkt aus Rechenzeit und der Anzahl der Prozessoren.

In der Schaltkreiskomplexität wird NC mithilfe von Schaltkreisen definiert. Für alle ${\displaystyle i\in \mathbb {N} }$ sei ${\displaystyle {\mbox{NC}}^{i}}$ die Klasse aller Sprachen, die von einer uniformen Schaltkreisfamilie mit polynomieller Größe, Tiefe ${\displaystyle {\mathcal {O}}\left(\log ^{i}(n)\right)}$ und einen Fan-In von höchstens 2 erkannt werden. Dann ist ${\displaystyle {\mbox{NC}}=\bigcup _{i=0}^{\infty }{\mbox{NC}}^{i}}$.[1] Uniformes NC enthält die Sprachen, die von LOGSPACE-uniformen NC-Familien erkannt werden.[2]

Erläuterung

Zusammengefasst u​nd vereinfacht bedeutet dies: Man betrachtet e​in Problem d​ann als effizient lösbar d​urch eine parallel arbeitende Maschine, w​enn die Problemlösung i​n logarithmischer Zeit erfolgen kann. Zum Vergleich s​ei angemerkt, d​ass man b​ei sequentiell arbeitenden Maschinen e​in Problem d​ann als effizient lösbar betrachtet, w​enn die Problemlösung i​n polynomialer Zeit erfolgen kann.

Auf e​iner sequentiell arbeitenden Maschine m​it nur e​inem Prozessor i​st die Zeitkomplexität gleich d​er Aufwandskomplexität. Umgekehrt bezeichnet d​er Aufwand a​uf einer parallel arbeitenden Maschine gerade d​ie Zeit, d​ie eine sequentiell arbeitende Maschine für d​ie Berechnung benötigt.

Hierarchie

Für alle ${\displaystyle i\in \mathbb {N} }$ gilt offensichtlich

${\displaystyle {\mbox{NC}}^{i}\subseteq {\mbox{NC}}^{i+1}}$

Es ist bekannt, dass darüber hinaus ${\displaystyle {\mbox{NC}}^{0}\subsetneq {\mbox{NC}}^{1}}$ gilt. Ansonsten ist aber unbekannt, ob die Inklusion echt ist. Betrachtet man nur monotone ${\displaystyle {\mbox{NC}}^{i}}$-Schaltkreise, ist die Inklusion immer echt.[3]

Verhältnis zu anderen Komplexitätsklassen

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 ${\displaystyle {\mbox{NC}}\subseteq {\mbox{P}}}$, es ist jedoch unklar, ob auch ${\displaystyle {\mbox{NC}}\supseteq {\mbox{P}}}$ und somit ob ${\displaystyle {\mbox{NC}}={\mbox{P}}}$ gilt. Man geht im Allgemeinen davon aus, dass NC eine echte Teilmenge von P ist, also ${\displaystyle {\mbox{NC}}\subsetneq {\mbox{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 ${\displaystyle {\mbox{NC}}={\mbox{P}}}$. Aufgrund der Vermutung ${\displaystyle {\mbox{NC}}\neq {\mbox{P}}}$ geht man also davon aus, dass es kein P-vollständiges Problem in NC gibt.

Weitere Klassen

• Es gilt NC = AC, darüber hinaus gilt für alle ${\displaystyle i\in \mathbb {N} }$: ${\displaystyle {\mbox{NC}}^{i}\subseteq {\mbox{AC}}^{i}\subseteq {\mbox{NC}}^{i+1}}$. Ein analoger Bezug gilt zur TC-Hierarchie. Im Falle ${\displaystyle i=0}$ gilt: ${\displaystyle {\mbox{NC}}^{0}\subsetneq {\mbox{AC}}^{0}\subsetneq {\mbox{NC}}^{1}}$. Dies folgt dabei daraus, dass NC⁰ keine Funktion berechnen kann, die von allen Eingabebits abhängt, womit die zwei Klassen von Problemen getrennt werden, die offensichtlich in AC⁰ liegen und von allen Bits abhängen, etwa der Oder-Funktion, und daraus, dass Parity nicht in AC⁰ liegt.
• Die Stufen der NC-Hierarchie verhalten sich wie folgt zu L und NL:[4]

${\displaystyle {\mbox{NC}}^{1}\subseteq {\mbox{L}}\subseteq {\mbox{NL}}\subseteq {\mbox{NC}}^{2}\subseteq {\mbox{NC}}}$

• In der deskriptiven Komplexitätstheorie entspricht NC der Klasse ${\displaystyle FO\left[\log(n)^{{\mathcal {O}}(1)}\right]}$.[5]

Literatur

• Sanjeev Arora und Boaz Barak: Computational Complexity. A Modern Approach. Cambridge University Press, Cambridge 2009, ISBN 978-0-521-42426-4.
• Stasys Jukna: Boolean function complexity. Advances and frontiers. Springer, 2012, ISBN 978-3-642-24507-7.
• Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass. 1995, ISBN 0-201-53082-1.

Weblinks

• NC. In: Complexity Zoo. (englisch)

Einzelnachweise

1. Definition folgt https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nc Die Uniformität wird nicht immer vorausgesetzt.
2. Sanjeev Arora und Boaz Barak: Computational Complexity. A Modern Approach. Cambridge University Press, Cambridge 2009, ISBN 978-0-521-42426-4., Seite 117
3. R. Raz und P. McKenzie: Separation of the monotone NC hierarchy. In: Combinatorica. Band 19, Nr. 3. Springer, 1999, S. 403–435 (psu.edu [PDF]).
4. Papadimitriou 1994, Theorem 16.1
5. https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nc