NC (Komplexität)

Ungelöstes Problem in der Informatik:

(mehr ungelöste Probleme in der Informatik)

Im Computerkomplexitätstheorie, die Klasse NC (für "Nicks Klasse") ist der Satz von Entscheidungsprobleme entschlossen in Polylogarithmische Zeit auf einen Parallele Computer mit einer Polynomzahl von Prozessoren. Mit anderen Worten, ein Problem ist in NC Wenn es Konstanten gibt c und k so dass es rechtzeitig gelöst werden kann O(Protokollc n) Verwendung O(nk) Parallelprozessoren. Stephen Cook[1][2] geprägt den Namen "Nick's Class" danach Nick Penpfger, wer hatte umfangreiche Forschungen durchgeführt[3] auf Schaltungen mit polylogarithmischer Tiefe und Polynomgröße.[4]

Genau wie die Klasse P kann als die folgenden Probleme betrachtet werden (Cobhams These), Also NC kann als die Probleme betrachtet werden, die auf einem parallelen Computer effizient gelöst werden können.[5] NC ist eine Teilmenge von P Da polylogarithmische parallele Berechnungen durch polynomiale sequentielle Simulierung simuliert werden können. Es ist nicht bekannt, ob NC = PAber die meisten Forscher vermuten, dass dies falsch ist, was bedeutet, dass es wahrscheinlich einige folgende Probleme gibt, die "von Natur aus sequentiell" sind und nicht mit der Parallelität signifikant beschleunigt werden können. Genau wie die Klasse NP-Complete kann als "wahrscheinlich unlösbar" angesehen werden, also die Klasse P-Complete, beim Benutzen NC Reduktionen können als "wahrscheinlich nicht parallelisierbar" oder "wahrscheinlich von Natur aus sequentiell" angesehen werden.

Der parallele Computer in der Definition kann als a angenommen werden Parallele, Zufallszugriffsmaschine (KINDERWAGEN). Dies ist ein paralleler Computer mit einem zentralen Speicherpool, und jeder Prozessor kann in konstanter Zeit auf jeden Speicherspeicher zugreifen. Die Definition von NC wird nicht von der Wahl beeinflusst, wie der Kinderwagen den gleichzeitigen Zugriff auf ein einzelnes Bit von mehr als einem Prozessor behandelt. Es kann CRCW, Crew oder Erew sein. Sehen KINDERWAGEN für Beschreibungen dieser Modelle.

Äquivalent, NC kann definiert werden als diese Entscheidungsprobleme, die von a leuchten einheitlicher boolescher Schaltkreis (Was aus der Länge des Eingangs für NC berechnet werden kann, können wir den Booleschen Schaltkreis der Größe berechnen n im logarithmischen Raum in n) mit Polylogarithmic Tiefe und eine Polynomzahl von Toren mit einem maximalen Lüfter von 2.

RNC Ist eine Klasse, die sich erstreckt NC mit Zugang zu Zufälligkeit.

Probleme in NC

Wie mit PDurch einen leichten Sprachmissbrauch kann man Funktionsprobleme klassifizieren und Probleme suchen NC. NC Es ist bekannt, dass viele Probleme enthalten sind, einschließlich

Oft mussten Algorithmen für diese Probleme getrennt erfunden werden und konnten nicht naiv von bekannten Algorithmen angepasst werden- Gaußsche Eliminierung und Euklidischer Algorithmus stützen sich auf die nacheinander ausgeführte Operationen. Man könnte kontrastieren Ripple Carry Adder mit einer Carry-Lookahead Addierer.

Beispiel

Ein Beispiel für ein Problem in NC1 Ist die Paritätsprüfung auf einer Bit -Zeichenfolge.[6] Das Problem besteht darin, die Anzahl der 1s in einer Zeichenfolge aus 1 und 0 zu zählen. Eine einfache Lösung besteht darin, alle Bits der Saiten zu summieren. Seit Zusatz ist assoziativ, . Bei rekursiven Anwenden einer solchen Eigenschaft ist es möglich, a zu bauen Binärbaum von Länge in der jede Summe zwischen zwei Bits und ist durch grundlegendes ausdrucksfähig logische Operatoren, z.B. durch den booleschen Ausdruck .

Die NC -Hierarchie

NCi ist die Klasse von Entscheidungsproblemen, die durch einheitliche booleale Schaltkreise mit einer Polynomzahl von Toren von höchstens zwei Eingaben und Tiefe entnommen werden können O(Protokolli n), oder die Klasse von Entscheidungsproblemen, die rechtzeitig lösbar sind O(Protokolli n) auf einem parallele Computer mit einer Polynomzahl von Prozessoren. Klar haben wir

das bildet die NC-Hierarchie.

Wir können die erzählen NC Klassen zu den Weltraumkursen L und Nl[7] und AC.[8]

Die NC-Klassen beziehen sich auf die Wechselstromklassen, die ähnlich definiert sind, aber mit Gatern, die den Fan-In unbegrenzt haben. Für jeden i, wir haben[5][8]

Als unmittelbare Folge davon haben wir das NC = AC.[9] Es ist bekannt, dass beide Einschlüsse streng sind i = 0.[5]

Ebenso haben wir das NC entspricht den Problemen, die auf einem löslich sind Wechsel Turing Machine beschränkt auf höchstens zwei Optionen bei jedem Schritt mit O(Protokoll n) Raum und Wechsel.[10]

Offenes Problem: Ist NC richtig?

Eine wichtige offene Frage in Komplexitätstheorie ist, ob jede Eindämmung in der NC Hierarchie ist richtig. Es wurde von Papadimitriou das beobachtet, wenn NCi = NCi+1 für einige i, dann NCi = NCj für alle j≥i, und als Ergebnis, NCi = NC. Diese Beobachtung ist bekannt als NC-Hierarchie kollaps

impliziert, dass das Ganze NC Hierarchie "bricht" auf eine gewisse Ebene zusammen i. Somit gibt es 2 Möglichkeiten:

Es wird allgemein angenommen, dass (1) der Fall ist, obwohl noch kein Beweis für die Wahrheit einer beiden Aussagen entdeckt wurde.

NC0

Die besondere Klasse NC0 arbeitet nur auf einer konstanten Länge der Eingangsbits. Es wird daher als die Klasse von Funktionen beschrieben, die durch einheitliche booleale Schaltkreise mit konstanter Tiefe und begrenztem Fan-In definierbar sind.

Barringtons Satz

A Verzweigungsprogramm mit n Variablen der Breite k und Länge m besteht aus einer Sequenz von m Anweisungen. Jede der Anweisungen ist ein Tupel (i, p, q) wo i ist der überprüfende Variablenindex (1 ≤ i ≤ n), und p und q sind Funktionen aus {1, 2, ..., k} bis {1, 2, ...,, k}. Zahlen 1, 2, ..., k werden Zustände des Verzweigungsprogramms genannt. Das Programm startet zunächst in Zustand 1 und jeder Anweisung (i, p, q) ändert den Zustand von x zu p(x) oder q(x), je nachdem, ob die iDie Variable beträgt 0 oder 1. Die Funktion, die einen Eingang in einen endgültigen Status des Programms zuordnet Ertrag des Programms (genauer gesagt, ist die Ausbeute einer Eingabe der Funktionszugriff, der jeden Anfangszustand in den entsprechenden endgültigen Zustand abbildet). Das Programm Akzeptiert ein Satz von variablen Werten, wenn es einige Funktionen gibt so dass eine variable Sequenz ist in A genau dann, wenn sein Ertrag in ist F.

Eine Familie von Verzweigungsprogrammen besteht aus einem Verzweigungsprogramm mit n Variablen für jeweils n. Es akzeptiert eine Sprache, wenn die n Das variable Programm akzeptiert die auf Länge beschränkte Sprache n Eingänge.

Es ist leicht zu zeigen, dass jede Sprache L Auf {0,1} kann durch eine Familie von Verzweigungsprogrammen mit Breite 5 und exponentieller Länge oder von einer Familie mit exponentieller Breite und linearer Länge erkannt werden.

Jede reguläre Sprache auf {0,1} kann von einer Familie von Verzweigungsprogrammen mit konstanter Breite und linearer Anzahl von Anweisungen erkannt werden (da ein DFA in ein Verzweigungsprogramm umgewandelt werden kann). BWBP bezeichnet die Klasse von Sprachen, die durch eine Familie von Verzweigungsprogrammen mit begrenzter Breite und Polynomlänge erkennbar sind.[11]

Barringtons Satz[12] sagt, dass BWBP ist genau ungleichmäßig NC1. Der Beweis verwendet die Nicht -Solvabilität der symmetrischen Gruppe s5.[11]

Der Satz ist ziemlich überraschend. Zum Beispiel impliziert dies, dass die Mehrheitsfunktion Kann von einer Familie von Verzweigungsprogrammen mit konstanter Breite und Polynomgröße berechnet werden, während die Intuition möglicherweise darauf hindeutet, dass man zur Erreichung einer Polynomgröße eine lineare Anzahl von Zuständen benötigt.

Beweis von Barringtons Theorem

Ein Verzweigungsprogramm mit konstanter Breite und Polynomgröße kann leicht (über Divide-and-Conquer) in eine Schaltung in umgewandelt werden NC1.

Nehmen Sie umgekehrt eine Schaltung in NC1 wird gegeben. Nehmen wir ohne Verlust der Allgemeinheit an, und und nicht von Toren.

Lemma 1-Wenn es ein Verzweigungsprogramm gibt, das manchmal als Permutation funktioniert P und manchmal als Permutation Qdurch rechte Multiplizierung von Permutationen in der ersten Anweisung von αund in der letzten Anweisung links multipliziert von βWir können eine Schaltung derselben Länge machen, die sich verhält wie βPα oder βQα, beziehungsweise.

Rufen Sie ein Verzweigungsprogramm α-Computer eine Schaltung an C Wenn es als Identität funktioniert, wenn CDie Ausgabe beträgt 0 und als α Wenn CDie Ausgabe ist 1.

Infolge von Lemma 1 und der Tatsache, dass alle Zyklen von Länge 5 sind konjugierenfür zwei beliebige 5-Zyklen α, β, wenn es ein Verzweigungsprogramm gibt, das eine Schaltung agr. Cund dann gibt es ein Verzweigungsprogramm, das die Schaltung β-Computering Caus der gleichen Länge.

Lemma 2-Es gibt 5 Zyklen γ, δ so dass ihre Kommutator ε=γδγ–1δ–1 ist ein 5-Zyklus. Zum Beispiel, γ = (1 2 3 4 5),, δ = (1 3 5 4 2) Geben ε = (1 3 2 5 4).

Nachweisen

Wir werden jetzt Barringtons Satz durch Induktion beweisen:

Angenommen, wir haben eine Schaltung C das nimmt Eingänge an x1, ...,xn und nehmen an, dass für alle Unterkreislauf D von C und 5 Zyklen α, es gibt ein Verzweigungsprogramm α-Computering D. Wir werden zeigen, dass für alle 5-Zyklen-α ein Verzweigungsprogramm α-Computing vorhanden ist C.

  • Wenn die Schaltung C gibt einfach ein Eingangsbit aus xiDas Verzweigungsprogramm, das wir benötigen, hat nur eine Anweisung: Überprüfung xiWert (0 oder 1) und Ausgabe der Identität oder α (beziehungsweise).
  • Wenn die Schaltung C Ausgänge ¬A Für eine andere Schaltung Aerstellen Sie ein Verzweigungsprogramm α–1-Computing A und dann die Ausgabe des Programms mit α multiplizieren. Von Lemma 1 erhalten wir ein Verzweigungsprogramm für A Ausgabe der Identität oder α, d.h. α-Computing ¬A=C.
  • Wenn die Schaltung C Ausgänge A∧B für Schaltungen A und Bschließen Sie sich den Verzweigungsprogrammen an, die γ-berechnen A, δ-berechnen B, γ–1-berechnen Aund δ–1-Compute B für eine Auswahl von 5 Zyklen γ und δ so, dass ihr Kommutator ε=γδγ–1δ–1 ist auch ein 5-Zyklus. (Das Vorhandensein solcher Elemente wurde in Lemma 2 festgelegt.) Wenn eines oder beide Schaltkreise 0 ausgeben, ist das resultierende Programm die Identität aufgrund von Stornierung; Wenn beide Schaltkreise 1 ausgeben, gibt das resultierende Programm den Kommutator aus ε. Mit anderen Worten, wir bekommen ein Programm ε-Computing A∧B. Da ε und α sind zwei 5 Zyklen, sie sind konjugiert, und daher gibt es ein Programm α-Computing A∧B von Lemma 1.

Durch die Annahme, dass die Unterkreislauf verzweigte Programme haben, damit sie es sind α-Verwendung für alle 5 Zyklen α∈S5wir haben gezeigt C hat diese Eigenschaft auch nach Bedarf.

Die Größe des Verzweigungsprogramms beträgt höchstens 4d, wo d ist die Tiefe der Schaltung. Wenn die Schaltung eine logarithmische Tiefe hat, hat das Verzweigungsprogramm eine Polynomlänge.

Anmerkungen

  1. ^ "Auf dem Weg zu einer Komplexitätstheorie der synchronen parallelen Berechnung. D l'Ensegnement Mathematique 27". {{}}: Journal zitieren erfordert |journal= (Hilfe)
  2. ^ Cook, Stephen A. (1985-01-01). "Eine Taxonomie von Problemen mit schnellen parallele Algorithmen". Informationen und Kontrolle. Internationale Konferenz über Grundlagen der Berechnungstheorie. 64 (1): 2–22. doi:10.1016/s0019-9958 (85) 80041-3. ISSN 0019-9958.
  3. ^ Penpfenger, Nicholas (1979). "Über gleichzeitige Ressourcengrenzen". 20. jährliches Symposium für Grundlagen der Informatik (SFCS 1979): 307–311. doi:10.1109/sfcs.1979.29. ISSN 0272-5428.
  4. ^ Arora & Barak (2009) S.120
  5. ^ a b c Arora & Barak (2009) S.118
  6. ^ David Mix Barrington; Alexis Maciel (2000-07-18). "Vortrag 2: Die Komplexität einiger Probleme" (PDF). IAS/PCMI Sommersitzung 2000 - Tonmathematik -Bachelor -Programm - Grundkurs zur Computerkomplexität. Clarkson University. Abgerufen 2021-11-11.
  7. ^ Papadimitriou (1994) Theorem 16.1
  8. ^ a b Clote & Kranakis (2002) S. 437
  9. ^ Clote & Kranakis (2002) S.12
  10. ^ S. Bellantoni und I. Oitavem (2004). "NC entlang der Deltaachse trennen". Theoretische Informatik. 318 (1–2): 57–78. doi:10.1016/j.tcs.2003.10.021.
  11. ^ a b Clote & Kranakis (2002) S. 50
  12. ^ Barrington, David A. (1989). "Begrenzungsbreite Polynomgröße Verzweigungsprogramme erkennen genau die Sprachen in NC1" (PDF). J. Comput. System. Sci. 38 (1): 150–164. doi:10.1016/0022-0000 (89) 90037-8. ISSN 0022-0000. Zbl 0667.68059.

Verweise