NC = P Konsequenzen?

35

Die Komplexität Zoo weist in dem Eintrag auf aus EXP , dass , wenn L = P dann PSPACE = EXP. Da NPSPACE = PSPACE von Savitch, so weit ich weiß, erweitert sich das zugrunde liegende Auffüllargument, um zu zeigen, dass Wir wissen auch, dass L NL NC P über die ressourcenbeschränkte alternierende Hierarchie von Ruzzo erfolgt.

(NL=P)(PSPACE=EXP).

Wenn NC = P, folgt daraus PSPACE = EXP?

Eine andere Interpretation der Frage im Sinne von Richard Lipton: Ist es wahrscheinlicher, dass einige Probleme in P nicht parallelisiert werden können, als dass keine Exponentialzeitprozedur mehr als Polynomraum erfordert?

Mich würden auch andere "überraschende" Folgen von NC = P interessieren (je unwahrscheinlicher, desto besser).

Edit: Ryans Antwort führt zu einer weiteren Frage: Was ist die schwächste Hypothese, die PSPACE = EXP garantiert?

  • W. Savitch. Beziehungen zwischen nicht deterministischen und deterministischen Bandkomplexitäten, Journal of Computer and System Sciences 4 (2): 177-192, 1970.
  • WL Ruzzo. Über die Komplexität einheitlicher Schaltkreise, Journal of Computer and System Sciences 22 (3): 365-383, 1971.

Bearbeiten (2014): Der alte Zoo-Link wurde aktualisiert und Links für alle anderen Klassen wurden hinzugefügt.

András Salamon
quelle
1
Wie ich bin sicher , die ich bin nicht nur ein nicht zu wissen , was NC ist, hier ein Link: en.wikipedia.org/wiki/NC_%28complexity%29
Emil
@Andras: Eine andere Konsequenz , die vielleicht haben Sie bereits wissen, hat aber noch nicht erwähnt worden ist , ist , dass die dann NC Hierarchie würde zusammenbrechen, da P vollständige Probleme unter hat L -Reduktionen.
Joshua Grochow

Antworten:

28

Ja. kann als die Klasse von Sprachen angesehen werden, die von alternierenden Turing-Maschinen erkannt werden, die O ( log n ) Raum und ( log n ) O ( 1 ) Zeit verwenden. (Dies wurde zuerst von Ruzzo bewiesen.) P ist die Klasse, in der alternierende Turing-Maschinen O ( log n ) -Raum verwenden, jedoch bis zu n O ( 1 ) Zeit benötigen können. Nennen wir der Kürze halber diese Klassen A T I S P [ ( log nNCO(logn)(logn)O(1)PO(logn)nO(1) und A S P A C E [ O ( log n ) ] = P .ATISP[(logn)O(1),logn]=NCASPACE[O(logn)]=P

Angenommen, die beiden Klassen sind gleich. Durch Ersetzen des durch 2 n im obigen Beispiel (dh Anwenden von Standardübersetzungs-Lemmas) erhält mann2n

.TIME[2O(n)]=ASPACE[O(n)]=ATISP[nO(1),n]ATIME[nO(1)]=PSPACE

Wenn dann gilt auch E X P = P S P A C E , da es in T I M E [ 2 O E X P -komplette Sprachen gibt ( n ) ] .TIME[2O(n)]PSPACEEXP=PSPACEEXPTIME[2O(n)]

Bearbeiten: Obwohl die obige Antwort vielleicht lehrreicher ist, ist hier ein einfacheres Argument: folgt bereits aus " P ist im Polylograum enthalten" und Standardübersetzung. EXP=PSPACEPNote „ wird in polylog Raum enthält“ ist eine viel schwächere Hypothese als N C = P .PNC=P

Weitere Details: Da Schaltung Familien Tiefe ( log n ) c für eine Konstante, kann jede solche Schaltung Familie in ausgewertet werden O ( ( log n ) c ) Raum. Daher N C c > 0 S P A C E [ ( log n ) c ] . Also impliziert P = N C P c > 0 SNC(logn)cO((logn)c)NCc>0SPACE[(logn)c]P=NC . Anwenden Übersetzung (ersetzt n mit 2 n schon sagt) T I M E [ 2 O ( n ) ] P S P A C E . Die Existenz einer E X P -kompletten Sprache in T I M E [ 2 O ( n ) ] beendet das Argument.Pc>0SPACE[(logn)c]n2nTIME[2O(n)]PSPACEEXPTIME[2O(n)]

Update: Bei Andreas 'zusätzlicher Frage sollte es meines Erachtens möglich sein, Folgendes zu beweisen: Wenn für alle c jede polynomial spärliche Sprache in n O ( log c n ) Zeit lösbar ist Polylog-Speicherplatz. (Als polynomial sparse bedeutet , dass es höchstens sind p o l y ( n ) Zeichenketten der Länge n in der Sprache, für alle nEXP=PSPACEcnO(logcn)poly(n)nnWenn dies zutrifft.), Wäre der Beweis wahrscheinlich gehen entlang der Linien von Hartmanis, Immerman und der Nachweis des Sewelson dass iff jeder polynomial spärliche Sprache in N P in enthalten ist , P . (Beachten Sie, dass die Zeit n O ( log c n ) im Polylog-Raum immer noch ausreicht, um P S P A C E = E X P zu implizieren .)NE=ENPPnO(logcn)PSPACE=EXP

Ryan Williams
quelle
1
Danke für die nette Antwort. Die Berechnungstheorie von Dexter Kozen hat eine schöne "einheitliche" Notation für Ruzzos Klassen auf Seite 69: wobei f den Raum, g die Zeit und h die Abwechslung begrenzt. Dann ist NC = S T A ( log n , , ( log n ) O ( 1 ) ), während P = S T A (STA(f,g,h)fghNC=STA(logn,,(logn)O(1)) was die Konstruktion wirklich hervorhebt. P=STA(logn,,)
András Salamon
1
Beachten Sie, dass ich oben sage . Ich denke jedoch, das sind die gleichen. Eine Maschine, die Polynomzeit und O ( log n ) Raum benötigt, aber nur ( log n ) O ( 1 ) Änderungen vornimmt, kann in eine andere alternierende Maschine umgewandelt werden, die nur ( log n ) O ( 1) benötigtNC=STA(logn,(logn)O(1),)O(logn)(logn)O(1) Zeit undO(logn)Raum. (Die andere Richtung liegt auf der Hand.) Die Idee ist, mehr Abwechslungen einzufügen, so dass jede Polynomzeit-Existenzphase und Universalphase "beschleunigt" wird, um nur in(logn ) O ( 1 ) Zeit undO(logn)Raumzu laufennach dem Satz von Savitch. (logn)O(1)O(logn)(logn)O(1)O(logn)
Ryan Williams
6
Was wir brauchen, ist eine Art Greasemonkey-Skript, das automatisch so etwas wie "\ NP" mit dem Eintrag im Zoo verknüpft.
Suresh Venkat
12

(Ich habe Ryans Antwort gesehen, wollte aber nur eine andere Perspektive angeben, die zu lang war, um in einen Kommentar zu passen.)

Im Beweis, alles , was Sie über L wissen müssen, informell ist, dass , wenn durch eine exponentielle gesprengt, L PSPACE wird. Der gleiche Beweis gilt für NL, da NL, das durch ein Exponential aufgeblasen wird, ebenfalls zu PSPACE wird. L=PPSPACE=EXP

In ähnlicher Weise erhalten Sie PSPACE, wenn NC durch eine Exponentialfunktion in die Luft gesprengt wird. Ich sehe das gerne in Bezug auf Schaltkreise: NC ist die Klasse von Schaltkreisen mit polynomischer Größe und Polylog-Tiefe. Wenn sie aufgeblasen werden, werden sie zu Schaltkreisen exponentieller Größe mit polynomieller Tiefe. Man kann zeigen, dass dies genau PSPACE ist, wenn die entsprechenden Gleichförmigkeitsbedingungen hinzugefügt wurden. Ich denke, wenn NC mit L-Gleichförmigkeit definiert ist, wird dies PSPACE-Gleichförmigkeit erhalten.

Der Beweis sollte einfach sein. Nehmen Sie in einer Richtung ein PSPACE-vollständiges Problem wie TQBF und drücken Sie die Quantifizierer mit UND- und ODER-Gattern exponentieller Größe aus. Versuchen Sie in der anderen Richtung, den Polynomtiefenkreis rekursiv zu durchlaufen. Die Stapelgröße ist polynomial, dies kann also in PSPACE erfolgen.

Schließlich kam ich auf dieses Argument, als ich die Frage sah (und bevor ich Ryans Antwort las), sodass es möglicherweise Fehler gab. Bitte weisen Sie darauf hin.

Robin Kothari
quelle
1
Eine Korrektur: NC hat Schaltkreise mit Polynomgröße und Polylog-Tiefe, aber dies ist nach der Translation immer noch nur Polynomtiefe.
Ryan Williams
@ Ryan: Du hast recht. Ich werde das reparieren.
Robin Kothari
1

Hier ist ein wenig mehr Detail aus der Perspektive der Simulation einer zeitlich-räumlich begrenzten Alternating Turing-Maschine.

Nehmen wir an, dass .P=NC

Da , erhalten wir P = A T I S P ( ( log ( N ) ) O ( 1 ) , O ( log ( n ) ) ) .NC=ATISP((log(n))O(1),O(log(n)))

P=ATISP((log(n))O(1),O(log(n))).

Betrachten wir nun das universelle Simulationsproblem der linearen Zeit bei dem wir eine Codierung auf einer Turing-Maschine M und eine Eingabezeichenfolge x der Länge n erhalten und wissen möchten, ob M x in höchstens n Schritten akzeptiert .LinUMxnMxn

Wir wissen , dass . Daher existiert eine Konstante c (ausreichend groß), so dass ( )LinUPc

()LinUATISP(logc(n),clog(n)).

(1)DTIME(n)ATISP(logc(n),clog(n)).

(2)DTIME(nk)ATISP(kclogc(n),kclog(n)).
(3)DTIME(2nk)ATISP(kcnkc,kcnk).

ATISP(logc(n),clog(n))DSPACE(O(logc+1(n))).

k

(2)DTIME(nk)DSPACE(kc+1logc+1(n))
(3)DTIME(2nk)DSPACE(nk(c+1)).

(3)EXP=PSPACE

=================== Nach dem Gedanken ===================

P=NC

ATISP((log(n))O(1),O(log(n)))=ATISP(logc(n),O(log(n)))
c

Kommentare oder Korrekturen sind willkommen. :)

Michael Wehar
quelle
1
NCkPSPACEkNC2PSPACENCPSPACE
1
NCPSPACEPuniformNC1=PSPACE
1
NC=ATISP((log(n))O(1),O(log(n)))
1
@Turbo Danke für das Follow-up !! Ich denke wirklich, dass Sie die Definition am Ende der Seite 370 von folgender
Adresse
1
NCPNC