Einige Fragen zum parallelen Rechnen und zur Klasse NC

Ich habe eine Reihe verwandter Fragen zu diesen beiden Themen.

Erstens, nur die meisten Komplexität Texte über die Klasse Glanz . Gibt es eine gute Ressource, die die Forschung ausführlicher behandelt? Zum Beispiel etwas, das alle meine folgenden Fragen behandelt. Außerdem gehe ich davon aus, dass N C aufgrund seiner Parallelisierung immer noch einiges an Forschung vorfindet, aber ich könnte mich irren. Der Abschnitt im Komplexitätszoo ist keine große Hilfe.$\mathbb{NC}$$\mathbb{NC}$

Zweitens befindet sich die Berechnung über eine Halbgruppe in wenn angenommen wird, dass die Halbgruppenoperation eine konstante Zeit benötigt. Aber was ist, wenn die Operation keine konstante Zeit benötigt, wie dies bei unbegrenzten ganzen Zahlen der Fall ist? Gibt es bekannte N C i -vollständige Probleme?$\mathbb{NC}^1$$\mathbb{NC}^i$

Drittens, gibt es seit einen Algorithmus, um einen beliebigen Logspace-Algorithmus in eine parallele Version umzuwandeln?$\mathbb{L} \subseteq \mathbb{NC}^2$

Viertens, es klingt wie die meisten Menschen gehen davon aus, dass die in der gleichen Art und Weise , dass P ≠ N P . Was ist die Intuition dahinter?$\mathbb{NC} \ne \mathbb{P}$$\mathbb{P} \ne \mathbb{NP}$

Fünftens erwähnt jeder Text, den ich gelesen habe, die Klasse , gibt jedoch keine Beispiele für darin enthaltene Probleme. Sind da irgendwelche?$\mathbb{RNC}$

Schließlich werden in dieser Antwort Probleme mit der sublinearen parallelen Ausführungszeit in erwähnt . Was sind einige Beispiele für diese Probleme? Gibt es andere Komplexitätsklassen , die parallele Algorithmen enthalten , die nicht bekannt sind , in sein N C ?$\mathbb{P}$$\mathbb{NC}$

Drittens, gibt es seit einen Algorithmus, um einen beliebigen Logspace-Algorithmus in eine parallele Version umzuwandeln?$\sf{L} \subseteq \sf{NC}^2$

Es kann ein gegebene gezeigt (Arora und Barak Lehrbuch) wird -Zeit TM M , daß ein oblivious TM M ' (dh ein TM , deren Kopfbewegung ist unabhängig von seinem Eingang x ) kann eine Schaltung konstruieren C n berechnen M ( x ) , wo | x | = n .$t(n)$$M$$M'$$x$$C_n$$M(x)$$|x| = n$

Der Beweis Skizze ist entlang der Linien von mit Simulieren M und der Definition von „Schnappschüssen“ der Zustand (dh Kopfpositionen, Symbolen am Kopf) in jedem Zeitschritt t i (man denke an eine Rechen log). Jeder Schritt t i kann aus x und dem Zustand t i - 1 berechnet werden . Da jeder Schnappschuss nur eine Zeichenfolge mit konstanter Größe enthält und nur eine konstante Anzahl von Zeichenfolgen dieser Größe vorhanden ist, kann der Schnappschuss bei t i von einer Schaltung mit konstanter Größe berechnet werden.$M'$$M$$t_i$$t_i$$x$$t_{i-1}$$t_i$

Wenn Sie die Schaltkreise konstanter Größe für jedes , haben wir einen Schaltkreis, der M ( x ) berechnet . Zusammen mit der Einschränkung, dass die Sprache von M in L ist , sehen wir, dass unsere Schaltung C n per Definition lograumuniform ist , wobei Homogenität nur bedeutet, dass unsere Schaltungen in unserer Schaltungsfamilie { C n } M ( x ) berechnen. Alle haben den gleichen Algorithmus. Kein maßgeschneiderter Algorithmus für jede Schaltung, die mit der Eingangsgröße n arbeitet .$t_i$$M(x)$$M$$\sf{L}$$C_n$$\{C_n\}$$M(x)$$n$

Wiederum aus der Definition der Gleichförmigkeit sehen wir , dass Schaltungen jede Sprache in der Entscheidung , eine Funktion haben , müssen Größe ( n ) berechenbar in O ( log n ) . Die Schaltkreisfamilie A C 1 hat höchstens die Tiefe O ( log n ) .$\sf{L}$$\text{size}(n)$$O(\log n).$$\sf{AC}^1$$O(\log n)$

Schließlich kann gezeigt werden, dass die fragliche Beziehung ergibt.$\sf{AC}^1 \subseteq \sf{NC}^2$

Viertens, es klingt so, als würden die meisten Leute annehmen, dass genauso ist wie $\sf{NC} \neq \sf{P}$ . Was ist die Intuition dahinter?$\sf{P} \neq \sf{NP}$

Bevor wir fortfahren , definieren wir, was Vollständigkeit bedeutet.$\sf{P}$

Eine Sprache ist P -komplett, wenn L ∈ P und jede Sprache in P ein auf sie reduzierbarer logarithmischer Raum ist. Außerdem, wenn L ist P -Complete dann die folgenden Bedingungen erfüllt sind$L$$\sf{P}$$L \in \sf{P}$$\sf{P}$$L$$\sf{P}$

1. $L \in \sf{NC} \iff \sf{P} = \sf{NC}$

2. $L \in \sf{L} \iff \sf{P} = \sf{L}$

Nun betrachten wir als die Klasse von Sprachen, die von einem Parallelcomputer (unserer Schaltung) effizient bestimmt wird. Es gibt einige Probleme in P , die einem Parallelisierungsversuch zu widerstehen scheinen (z. B. ein lineares Programmier- und ein Schaltungswertproblem). Das heißt, bestimmte Probleme erfordern eine schrittweise Berechnung.$\sf{NC}$$\sf{P}$

Beispielsweise ist das Schaltkreiswertproblem wie folgt definiert:

Was ist bei gegebener Schaltung , Eingang x und einem Gatter g ∈ C der Ausgang von g an C ( x ) ?$C$$x$$g \in C$$g$$C(x)$

Wir wissen nicht, wie wir dies besser berechnen können, als alle Tore zu berechnen , die vor g kommen . Vorausgesetzt, einige von ihnen können parallel berechnet werden, zum Beispiel, wenn sie alle zu einem bestimmten Zeitpunkt t i auftreten , aber wir wissen nicht, wie die Ausgabe von Toren zu dem Zeitpunkt t i und dem Zeitpunkt t i + 1 für die offensichtliche Schwierigkeit berechnet wird dass Tore bei t i + 1 die Ausgabe von Toren bei t i erfordern !$g'$$g$$t_i$$t_i$$t_{i+1}$$t_{i+1}$$t_i$

Dies ist die Intuition hinter .$\sf{NC} \neq \sf{P}$

Limits to Parallel Computation ist ein Buch über Vollständigkeit in ähnlicher Weise wie Garey & Johnsons N P- Vollständigkeitsbuch.$\sf{P}$$\sf{NP}$

Fünftens erwähnt jeder Text, den ich gelesen habe, die Klasse RNC, gibt jedoch keine Beispiele für darin enthaltene Probleme. Sind da irgendwelche?

$\mathbb{RNC}^2$