Exponentielles Analogon von NC?

8

Nicks Klasse (NC) ist die Klasse von Problemen, die in Poly-Log-Zeit unter Verwendung einer Polynomzahl von Prozessoren entschieden werden können.

Ich möchte etwas über das exponentielle Analogon wissen, das Probleme abdeckt, die in Polynomzeit unter Verwendung einer exponentiellen Anzahl von Prozessoren entschieden werden können.

Was ich suche, ist ein Name für diese Klasse und alle bekannten Beziehungen zwischen dieser Klasse und anderen Komplexitätsklassen oder irgendwelche kanonischen Probleme für die Klasse. Es scheint unkompliziert zu sein, dass es NP und Co-NP enthalten würde, und ich denke, es ist in PSPACE enthalten, aber ich bin mir nicht sicher, ob es noch viel anderes gibt.

complexity-theory reference-request parallel-computing complexity-classes Kurt Müller
quelle
8
Ich schrieb eine Antwort, fand sie dann aber hier beantwortet: cstheory.stackexchange.com/questions/6753/…
mdxn

Antworten:

1

Die Zeit in Schaltkreisen entspricht der Tiefe. Daher bedeutet Polynomzeit Polynomtiefe.

Die Anzahl der Prozessoren entspricht der Größe der Schaltung, dh der Anzahl der Gates in der Schaltung. Durch die exponentielle Anzahl von Prozessoren erlauben Sie also eine exponentielle Größe. Dies wäre die KlasseD.epthS.ichze(nÖ(1),2nÖ(1))D.epthS.ichze(2,2nÖ(1))

Das Problem ist, dass die exponentielle Anzahl von Prozessoren zu stark ist, um für sich allein nützlich zu sein.

P.S.peinceP.S.peince=EINT.ichme(nÖ(1))Probleme, die durch abwechselnde Turing-Maschinen in Polynomzeit berechnet werden können. Der Wechsel in Turing-Maschinen besteht im Wesentlichen darin, neue Prozesse zu forken und nach dem Abschluss zu verbinden, indem die Konjunktion / Disjunktion ihrer Rückgabewerte vorgenommen wird.

Kaveh
quelle
Man bekommt PSPACE auch dann, wenn die einzige Einschränkung der Kommunikation die zeitgebundene ist.
@ Ricky, es kommt wirklich auf das Modell an. Wenn das Modell eine alternierende Turingmaschine ist, dann ja, wie ich in meiner Antwort geschrieben habe. Wenn es sich um allgemeine Schaltkreise handelt (die ungleichmäßigen NC-Schaltkreise), dann nicht. Die für Schaltungen gebundene Zeit ist die Tiefe und jede Funktion kann durch eine Tiefe von 2 CNF berechnet werden.
Kaveh
Das OP spezifizierte das Modell als Parallelmaschine.
@ Ricky, was meinst du mit "Parallelmaschine"? Es gibt viele Modelle, die versuchen, den Begriff der parallelen Berechnung zu erfassen. ZB PRAM nehmen . OP fragt nach NC, einer Klasse von Schaltkreisen, und schreibt, was ich angegeben habe.
Kaveh
Ich meine im Wesentlichen PRAM. Das OP sagt, dass NC "die Klasse von Problemen ist, die in der Poly-Log-Zeit unter Verwendung einer Polynomzahl von Prozessoren entschieden werden können", und fragt nach "Problemen, die in Polynomzeit unter Verwendung einer exponentiellen Anzahl von Prozessoren entschieden werden können".