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.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal O\left(\log^c n\right)} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} konstant) und mit polynomiell vielen (also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \in \N} sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{NC}^i} die Klasse aller Sprachen, die von einer uniformen Schaltkreisfamilie mit polynomieller Größe, Tiefe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal O\left(\log^i(n)\right)} und einen Fan-In von höchstens 2 erkannt werden. Dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{NC} = \bigcup_{i=0}^\infty \mbox{NC}^i } . Uniformes NC enthält die Sprachen, die von LOGSPACE-uniformen NC-Familien erkannt werden.

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.

Hierarchie

Für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \in \N} gilt offensichtlich

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{NC}^i \subseteq \mbox{NC}^{i+1}}

Es ist bekannt, dass darüber hinaus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{NC}^0 \subsetneq \mbox{NC}^{1}} gilt. Ansonsten ist aber unbekannt, ob die Inklusion echt ist. Betrachtet man nur monotone Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{NC}^i} -Schaltkreise, ist die Inklusion immer echt.

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{NC}\subseteq\mbox{P}} , es ist jedoch unklar, ob auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{NC}\supseteq\mbox{P}} und somit ob Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{NC} = \mbox{P}} gilt. Man geht im Allgemeinen davon aus, dass NC eine echte Teilmenge von P ist, also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{NC} = \mbox{P}} . Aufgrund der Vermutung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \in \N} : Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mbox{NC}^i \subseteq \mbox{AC}^i \subseteq \mbox{NC}^{i+1}} . Ein analoger Bezug gilt zur TC-Hierarchie. Im Falle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i=0} gilt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle FO\left[\log(n)^{\mathcal O(1)}\right]} .

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)