Was ist die große Version von NC?

$\mathsf{NC}$ fängt die Idee einer effizienten Parallelisierung ein, und eine Interpretation davon sind Probleme, die in der Zeit mit parallelen Prozessoren für einige Konstanten , lösbar sind . Meine Frage ist, ob es eine analoge Komplexitätsklasse gibt, in der die Zeit und die Anzahl der Prozessoren beträgt . Zum Ausfüllen der leeren Frage: $O(\log^c n)$ $O(n^k)$ $c$ $k$ $n^c$ $2^{n^k}$

$\mathsf{NC}$ ist zu als _ _ ist zu $\mathsf{P}$ $\mathsf{EXP}$

Insbesondere interessiere ich mich für ein Modell, bei dem eine exponentielle Anzahl von Computern in einem Netzwerk mit polynomial begrenztem Grad angeordnet ist (sagen wir, das Netzwerk ist unabhängig von der Eingabe / dem Problem oder zumindest leicht zu konstruieren oder von anderen vernünftigen Gleichförmigkeitsannahmen ). Zu jedem Zeitschritt:

Jeder Computer liest die Polynomzahl der polynomgroßen Nachrichten, die er im vorherigen Zeitschritt empfangen hat.
Auf jedem Computer wird eine Polytime-Berechnung ausgeführt, die von diesen Meldungen abhängen kann.
Jeder Computer gibt an jeden seiner Nachbarn eine Nachricht (mit einer bestimmten Länge) weiter.

Wie heißt eine Komplexitätsklasse, die diesen Modellen entspricht? Was ist ein guter Ort, um über solche Komplexitätsklassen zu lesen? Gibt es für eine solche Klasse vollständige Probleme?

cc.complexity-theory reference-request complexity-classes circuit-complexity dc.parallel-comp Artem Kaznatcheev
quelle

Zugehörige

Artem Kaznatcheev

Wir haben

N C^{k} = A S p a c e T i m e (O (\log n), (\log n)^{k})

$NC^k = ASpaceTime(O(\log n), (\log n)^k)$

N C = A S p a c e T i m e (O (\log n), (\log n)^{O (1)})

$NC = ASpaceTime(O(\log n), (\log n)^{O(1)})$

. Die zu

korrespondierende Klassekönnte also so etwas wie

P = T i m e (n^{O (1)})

$P = Time(n^{O(1)})$

E X P = T i m e (2^{n^{O (1)}})

$EXP = Time(2^{n^{O(1)}})$

N C^{k}

$NC^k$

und die entsprechende Klasse dann

wird

. Es ist nur eine algebraische Manipulation, ich habe nicht überprüft, ob sie Ihren Anforderungen entspricht, aber ich denke, dass sie die drei Bedingungen erfüllt, aber nicht über exponentiell viele Computer verfügt. Ich denke, Sie sollten diese Anforderung ansonsten fallen lassen (mehr)

A S p a c e T i m e (n^{O (1)}, 2^{O (\log n)^{k}})

$ASpaceTime(n^{O(1)}, 2^{O(\log n)^k})$

N C

$NC$

A S p a c e T i m e (n^{O (1)}, 2^{(\log n)^{O (1)}})

$ASpaceTime(n^{O(1)}, 2^{(\log n)^{O(1)}})$

Kaveh

Die resultierende Klasse wird

und die Analogie wird nicht als

E X P

$EXP$

N C \subseteq P

$NC \subseteq P$

Kaveh

Ich verstehe nicht, wo Sie bekam

den Raum Komplexität. Soweit ich weiß, erlaubt

polynomiell viele Tore. Wenn wir uns an Ihrem Analog orientieren möchten, sollten wir

als

und dann ist die Komplexitätsklasse, nach der ich suche, etwas wie

l o g n

$log n$

N C

$NC$

N C

$NC$

P T / W K (l o g^{c} n, n^{k}) / p o l y

$PT/WK(log^c n,n^k)/poly$

. Ich hatte jedoch gehofft, dass es eine bessere Charakterisierung gibt als diese.

P T / W K (n^{c}, 2^{n^{k}}) / p o l y

$PT/WK(n^c ,2^{n^k})/poly$

Artem Kaznatcheev

Das ist Standard (obwohl es nicht im Complexity Zoo ist), überprüfen Sie zB Ruzzo, "On uniform circuit complexity", 1981. Auch ich denke, Sie sollten mit einheitlichen Klassen arbeiten, jede Funktion hat exponentielle Größenwechsel / logische Tiefe 2 Schaltungen (und Dies wird die drei Bedingungen erfüllen, wenn wir begrenztes Fan-In und Tiefen-

) verwenden. Und wie gesagt, wenn es exponentiell viele Knoten gibt, dann gilt die Analogie nicht. Auch eine Haupteigenschaft der parallelen Berechnung wird Zeit gespart, es ist zB Poly-log Zeit im Fall von

. Ich denke, Quasi-Polynom-Zeit würde Poly-Log-Zeit entsprechen.

\log n

$\log n$

N C

$NC$

Kaveh

Antworten:

Ich glaube , die Klasse Sie suchen , ist . Angenommen, Sie haben Prozessoren, die die Anforderungen erfüllen: $PSPACE$ $exp(n^k) = 2^{O(n^k)}$

Jeder Computer liest die Polynomzahl der polynomgroßen Nachrichten, die er im vorherigen Zeitschritt empfangen hat.

Auf jedem Computer wird eine Polytime-Berechnung ausgeführt, die von diesen Meldungen abhängen kann.

Jeder Computer gibt an jeden seiner Nachbarn eine Nachricht (mit einer bestimmten Länge) weiter.

Dies kann mit einer Schaltung mit modelliert werden Schichten, wobei jede Schicht „gates“, und jedes „Gate“ funktioniert einen Polynom Zeitberechnung (befriedigend Teil 2) mit Polynom Fan-In (Teil 1) und Polynom-Fan-Out (Teil 3). $poly(n)$ $exp(n^k)$

Da jedes Gatter eine Polynomzeitfunktion berechnet, kann jede durch eine polynomgroße Schaltung (mit UND / ODER / NICHT) auf die übliche Weise ersetzt werden. Beachten Sie, dass die polynomiellen Fan-Ins und Fan-Outs auf 2 festgelegt werden können, indem die Tiefe nur um einen Faktor erhöht wird. Was bleibt , ist ein Tiefe einheitliche Schaltung mit UND / ODER / NICHT - Gatter. Dies ist genau die alternierende Polynomzeit, die genau . $O(\log n)$ $poly(n)$ $exp(n^k)$ $PSPACE$

Ryan Williams
quelle

Ryan, ich weiß nicht, wie Sie die exponentielle Anzahl von Computern in polynomiell viele Schichten einteilen. Es scheint mir, dass die Tiefe exponentiell sein kann. Können Sie es ein bisschen genauer erklären, warum dies möglich ist? Auch scheint mir der triviale Aufbau einer CNF-Schaltung einer beliebigen Funktion als Fan-In-2-Schaltung den Anforderungen zu genügen, fehle ich etwas?

Kaveh

@Kaveh: Ich verstehe deine erste Frage nicht. Obwohl es für jede Funktion eine Schaltung mit der Tiefe 2 in Exponentialgröße gibt, erfordert NC (Poly), dass Sie die Schaltungen einheitlich generieren können, damit Sie nicht für jede Eingangsgröße beliebige Schaltungen erzeugen können.

Robin Kothari

@ Robin, danke. Wahrscheinlich bin ich verwirrend. (Ich bin der Meinung, dass die Tiefe der Schaltkreise, die PSpace entsprechen, exponentiell sein sollte. Ich denke auch, dass PSpace EXP ist, so wie L für P ist. Dasselbe zu sagen, wenn L durch NC ersetzt wird, ist für mich seltsam. Ich denke, dass die Klasse, die wir sind Die Pflege sollte zwischen PSpace und EXP liegen.) Ich muss ein bisschen mehr nachdenken, um zu verstehen, was hier vor sich geht.

Kaveh

@Kaveh, ich habe die Anzahl der Ebenen (dh die Tiefe) als exponentiell zugewiesen, daher kann die Tiefe per Definition nicht exponentiell sein. Es gibt exponentiell viele Prozessoren, sodass Ihr CNF ein exponentielles Fan-In benötigt, wodurch eine der Bedingungen verletzt wird. Die Tiefe von Schaltkreisen mit Exponentialgröße, die PSPACE entsprechen, ist polynomiell. Der Grund dafür, dass dies zutrifft, und der Grund dafür, dass beide Analogien in gewisser Weise "gültig" sind ("PSPACE ist zu EXP wie L zu P" und "PSPACE ist zu EXP wie NC zu P"), ist, dass PSPACE = Alternating Polynom Zeit. Wir wissen nicht, ob L = alternierende logarithmische Zeit ist (dies ist NC1).

Ryan Williams

Ich denke, ich verstehe die Situation besser, nachdem ich Ihre und Robins Kommentare gelesen habe, danke.

Kaveh

Wie Ryan sagt, ist diese Klasse PSPACE. Diese Klasse wird in der Literatur häufig als NC (Poly) bezeichnet. Hier ist ein direktes Zitat aus dem QIP = PSPACE- Papier:

Wir betrachten eine vergrößerte Variante von NC, bei der es sich um die Komplexitätsklasse NC (poly) handelt, die aus allen Funktionen besteht, die durch polynomraumuniformierte Familien von Booleschen Schaltungen mit Polynomtiefe berechenbar sind. (Die Notation NC (2 ^poly ) wurde auch zuvor für diese Klasse verwendet [11].) Für Entscheidungsprobleme ist bekannt, dass NC (poly) = PSPACE [10].

[10] A. Borodin. Zeit und Raum in Beziehung setzen zu Größe und Tiefe. SIAM Journal on Computing, 6: 733–744, 1977.

[11] A. Borodin, S. Cook und N. Pippenger. Parallele Berechnung für gut ausgestattete Ringe und weltraumgebundene probabilistische Maschinen. Information and Control, 58: 113–136, 1983.

Eine Möglichkeit, dies zu sehen, besteht darin, beide Einschlüsse direkt zu beweisen. Um zu sehen, dass sich NC (poly) in PSPACE befindet, können wir die Ausgabe des endgültigen Gatters rekursiv berechnen und benötigen nur einen Stapel mit einer Größe, die der Tiefe der Schaltung entspricht, die polynomiell ist. Um zu zeigen, dass sich PSPACE in NC (poly) befindet, ist zu beachten, dass QBF, das PSPACE-vollständig ist, wie üblich als Polynomtiefenschaltung mit exponentiell vielen Gattern geschrieben werden kann - der existierende Quantifizierer ist ein ODER-Gatter, der Forall-Quantifizierer ist ein UND-Gatter. Da es nur polynomisch viele Quantifizierer gibt, handelt es sich um eine polynomische Tiefenschaltung.

Robin Kothari
quelle