In der Kompliziertheitstheorie die Klasse ist NC (für die "Klasse von Nick") der Satz von Entscheidungsproblemen, die in der polylogarithmischen Zeit auf einem parallelen Computer mit einer polynomischen Zahl von Verarbeitern entscheidbar sind. Mit anderen Worten ist ein Problem in NC, wenn dort Konstanten c und solcher k bestehen, dass es rechtzeitig O gelöst werden kann (loggen Sie n), O (n) parallele Verarbeiter verwendend. Stephen Cook hat den Namen "Nicks Klasse" nach Nick Pippenger ins Leben gerufen, der umfassende Forschung über Stromkreise mit der polylogarithmischen Tiefe und polynomischen Größe getan hatte.

Da von der Klasse P als die lenksamen Probleme gedacht werden kann (die These von Cobham), so kann von NC als die Probleme gedacht werden, die auf einem parallelen Computer effizient gelöst werden können. NC ist eine Teilmenge von P, weil polylogarithmische parallele Berechnung durch polynomisch-malige folgende vorgetäuscht werden kann. Es ist unbekannt, ob NC = P, aber die meisten Forscher verdächtigen das, falsch zu sein, meinend, dass es wahrscheinlich einige lenksame Probleme gibt, die "von Natur aus folgend sind" und durch das Verwenden des Parallelismus nicht bedeutsam beschleunigt werden können. Ebenso die Klasse kann von NP-Complete als "wahrscheinlich unnachgiebig" gedacht werden, so kann von der Klasse P-Complete, wenn man die NC Verminderungen verwendet, als "wahrscheinlich nicht parallelizable" oder "wahrscheinlich von Natur aus folgend" gedacht werden.

Wie man

annehmen kann, ist der parallele Computer in der Definition eine Parallele, Maschine des zufälligen Zugangs (PRAHM). Das ist ein paralleler Computer mit einer Hauptlache des Gedächtnisses, und jeder Verarbeiter kann auf jedes Bit des Gedächtnisses in der unveränderlichen Zeit zugreifen. Die Definition von NC wird durch die Wahl dessen nicht betroffen, wie der PRAHM Parallelzugriff zu einem einzelnen Bit durch mehr als einen Verarbeiter behandelt. Es kann CRCW, MANNSCHAFT oder EREW sein. Sieh PRAHM für Beschreibungen jener Modelle.

Gleichwertig kann NC als jene Entscheidungsprobleme definiert werden, die durch einen gleichförmigen Stromkreis von Boolean entscheidbar sind (der von der Länge des Eingangs berechnet werden kann) mit der polylogarithmischen Tiefe und einer polynomischen Zahl von Toren.

RNC ist eine Klasse, die NC mit dem Zugang zur Zufälligkeit erweitert.

Probleme in NC

Als mit P, durch einen geringen Missbrauch der Sprache, könnte man Funktionsprobleme klassifizieren und Probleme als seiend in NC suchen. Wie man bekannt, schließt NC viele Probleme einschließlich ein

• Hinzufügung der ganzen Zahl, Multiplikation und Abteilung;
• Matrixmultiplikation, Determinante, Gegenteil, Reihe;
• Polynomischer GCD, durch die Verminderung zur geradlinigen Algebra mit der Matrix von Sylvester (ist es offen, ob ganze Zahl GCD in NC ist);
• Die Entdeckung eines maximalen Zusammenbringens.

Häufig mussten Algorithmen für jene Probleme getrennt erfunden werden und konnten von wohl bekannten Algorithmen nicht naiv angepasst werden - Beseitigung von Gaussian und Euklidischer Algorithmus verlassen sich auf in der Folge durchgeführte Operationen. Man könnte sich abheben Kräuselung tragen Viper mit einer tragen-lookahead Viper.

Die NC Hierarchie

NC ist die Klasse von Entscheidungsproblemen, die durch die Uniform boolean Stromkreise mit einer polynomischen Zahl von Toren von höchstens zwei Eingängen entscheidbar sind, und Tiefe O (loggen Sie n), oder die Klasse von Entscheidungsproblemen lösbar rechtzeitig O (loggen Sie n) auf einem parallelen Computer mit einer polynomischen Zahl von Verarbeitern. Klar haben wir

:

der die NC-Hierarchie bildet.

Wir können die NC Klassen mit den Raumklassen L und NL verbinden. Von Papadimitriou 1994, Lehrsatz 16.1:

:

Ähnlich haben wir das NC ist zu den Problemen gleichwertig, die auf einer Wechselmaschine von Turing lösbar sind, die auf höchstens zwei Optionen an jedem Schritt mit dem Raum und den Wechseln eingeschränkt ist.

Offenes Problem: Ist NC richtig?

Eine größere geöffnete Frage in der Kompliziertheitstheorie ist, ob jede Eindämmung in der NC Hierarchie richtig ist. Es wurde von Papadimitriou dass, wenn NC = NC für einige ich, dann NC = NC für den ganzen j  i, und infolgedessen, NC = NC bemerkt. Diese Beobachtung ist als NC-Hierarchie-Zusammenbruch weil sogar eine einzelne Gleichheit in der Kette von Eindämmungen bekannt

:

deutet an, dass die komplette NC Hierarchie unten zu einem Niveau i "zusammenbricht". So gibt es 2 Möglichkeiten:

Es wird weit geglaubt, dass (1) der Fall ist, obwohl kein Beweis betreffs der Wahrheit jeder Behauptung noch entdeckt worden ist.

Der Lehrsatz von Barrington

Ein sich verzweigendes Programm mit n Variablen der Breite k und Länge M besteht aus einer Folge der M Instruktionen. Jede der Instruktionen ist ein Tupel (ich, p, q), wo ich der Index der Variable bin, um zu überprüfen (1 ≤ ich ≤ n), und sind p und q Funktionen von {1,2..., k} zu {1,2..., k}. Das Programm fängt am Anfang in staatlichem 1 an, und jede Instruktion (ich, p, q) ändert den Staat von x bis p (x) oder q (x), je nachdem, ob i-th Variable 0 oder 1 ist.

Eine Familie von sich verzweigenden Programmen besteht aus einem sich verzweigenden Programm mit n Variablen für jeden n.

Es ist leicht zu zeigen, dass jede Sprache L auf {0,1} mit einer Familie von sich verzweigenden Programmen der Breite 4 und Exponentiallänge, oder mit einer Familie der Exponentialbreite und geradlinigen Länge entschieden werden kann.

Jede regelmäßige Sprache auf {0,1} kann mit einer Familie von sich verzweigenden Programmen der unveränderlichen Breite und geradliniger Zahl von Instruktionen anerkannt werden (da ein DFA zu einem sich verzweigenden Programm umgewandelt werden kann).

Der Lehrsatz von Barrington sagt, dass die Klasse von Sprachen, die mit einer Familie von sich verzweigenden Programmen der Breite 5 und polynomische Länge anerkannt sind, genau ungleichförmiger NC ist. Der Beweis verwendet Nichtlösbarkeit der symmetrischen Gruppe S.

Der Lehrsatz ist ziemlich überraschend. Es deutet an, dass Majoritätsfunktion mit einer Familie von sich verzweigenden Programmen der unveränderlichen Breite und polynomischen Größe geschätzt werden kann, während Intuition darauf hinweisen könnte, dass, um polynomische Größe zu erreichen, man geradlinige Zahl von Staaten braucht.

Beweis des Lehrsatzes von Barrington

Ein sich verzweigendes Programm der unveränderlichen Breite und polynomischen Größe kann (über den teilen-und-überwinden) zu einem Stromkreis in NC leicht umgewandelt werden.

Nehmen Sie umgekehrt an, dass ein Stromkreis in NC gegeben wird. Ohne Verlust der Allgemeinheit, nehmen Sie an, dass es nur UND und NICHT Tore verwendet.

Lemma 1: Wenn dort ein sich verzweigendes Programm besteht, das manchmal als Versetzung P und manchmal als Q, durch Recht multiplizierende Versetzungen in der ersten Instruktion durch, und in der letzten Instruktion arbeitet, die dadurch nach links multipliziert, können wir einen Stromkreis derselben Länge machen, die sich wie oder beziehungsweise benimmt.

Nennen Sie ein sich verzweigendes Programm - Computerwissenschaft eines Stromkreises, wenn sie als Identität arbeitet, wenn die Produktion von C 0, und als ist, wenn die Produktion von C 1 ist.

Demzufolge des Lemmas 1 und die Tatsache, dass alle Zyklen der Länge 5 für irgendwelche zwei 5 Zyklen verbunden sind, wenn dort ein sich verzweigendes Programm - Computerwissenschaft eines Stromkreises C besteht, dann dort besteht ein sich verzweigendes Programm - Computerwissenschaft des Stromkreises C von derselben Länge.

Lemma 2: Dort besteht solche 5 Zyklen, dass ihr Umschalter ein 5-Zyklen-ist. Zum Beispiel.

Wir werden jetzt den Lehrsatz von Barrington durch die Induktion beweisen.

Nehmen Sie an, dass für alle Substromkreise und 5 Zyklen, dort ein sich verzweigendes Programm - Computerwissenschaft besteht. Wir werden zeigen, dass für alle 5 Zyklen, dort ein sich verzweigendes Programm - Computerwissenschaft besteht.

• Wenn die Stromkreis-Produktionen, das sich verzweigende Programm eine Instruktionsüberprüfung und outputting Identität oder beziehungsweise hat.
• Wenn die Stromkreis-Produktionen, wo ein verschiedener Stromkreis ist. Schaffen Sie ein sich verzweigendes Programm - Computerwissenschaft, und multiplizieren Sie Produktion des Programms (Lemma 1 verwendend), durch, ein sich verzweigendes Programm outputting oder, d. h. - Computerwissenschaft zu bekommen.
• Wenn die Stromkreis-Produktionen, sich den sich verzweigenden Programmen anschließen Sie, die - D schätzen, - schätzen C, - schätzen D, - schätzen C. Wenn eine der Stromkreis-Produktionen 0, das resultierende Programm Identität sein wird; wenn beide Stromkreis-Produktion 1, das resultierende Programm als arbeiten wird. Mit anderen Worten bekommen wir ein Programm - Computerwissenschaft. Weil und zwei 5 Zyklen sind, sind sie verbunden, und dort besteht ein Programm - Computerwissenschaft.

Die Größe des sich verzweigenden Programms ist höchstens, wo d die Tiefe des Stromkreises ist. Wenn der Stromkreis logarithmische Tiefe hat, hat das sich verzweigende Programm polynomische Länge.

• Greenlaw, Raymond, James Hoover und Walter Ruzzo. Grenzen, um Berechnung Anzupassen; P-Vollständigkeitstheorie. Internationale Standardbuchnummer 0-19-508591-4
• Heribert Vollmer. Einführung in die Stromkreis-Kompliziertheit - Eine Gleichförmige Annäherung. Internationale Standardbuchnummer 3-540-64310-9

• Abschnitt 15.3: Die Klasse NC, pp.375-381.

• Vorträge 28 - 34 und 36

• Vortrag 12: Beziehung von NC zu Zeitraumklassen