Hat L eine Definition in Bezug auf Schaltkreise?

Viele mit Turing-Maschinen definierte Komplexitätsklassen haben Definitionen in Bezug auf einheitliche Schaltkreise. Beispielsweise kann P auch unter Verwendung von Schaltkreisen mit einheitlicher Polynomgröße definiert werden, und in ähnlicher Weise können BPP, NP, BQP usw. mit einheitlichen Schaltkreisen definiert werden.

Gibt es also eine schaltungsbasierte Definition von L?

Eine naheliegende Idee wäre es, Schaltungen mit polynomischer Größe mit einer gewissen Tiefenbegrenzung zuzulassen, dies hat jedoch zur Folge, dass die NC-Hierarchie definiert wird.

Ich habe vor langer Zeit über diese Frage nachgedacht, aber keine Antwort gefunden. Wenn ich mich richtig erinnere, war meine Motivation zu verstehen, wie das Quantenanalog von L aussehen würde.

cc.complexity-theory complexity-classes circuit-complexity Robin Kothari
quelle

Enthalten Schaltkreise mit logarithmischer Größe ?

L

$L$

Mohammad Al-Turkistany

@Turkistany: Nein, das glaube ich nicht, da ein Schaltkreis mit logarithmischer Größe höchstens logarithmische Tiefe haben kann und daher in NC_1 enthalten ist, das als Schaltkreise mit logarithmischer Tiefe und poly-Größe definiert ist. NC_1 ist in L enthalten und es ist nicht bekannt, dass es L entspricht.

Robin Kothari

Antworten:

Nun, , wobei die Klasse von Sprachen ist, die durch Polynomgrößenschaltungen der Breite berechnet werden . $L = SC^1$ $SC^1$ $O(\log n)$

Was , könnte es als die Klassensprachen charakterisiert werden, die durch Polynomgrößen- Versatzschaltungen berechnet werden (was in gewissem Sinne nur eine andere Art ist, nicht deterministische Verzweigungsprogramme zu sagen). $NL$

Kristoffer Arnsfelt Hansen
quelle

Wir brauchen einheitliche Schaltkreise, oder?

Hsien-Chih Chang 張顯張顯

Richtig, sie sollten einheitlich sein.

Kristoffer Arnsfelt Hansen

S C^{1}

$SC^1$ wird unter Verwendung von Turingmaschinen als

so dass es bereits einheitlich ist.

D T i m e S p a c e (p o l y, l o g)

$DTimeSpace(poly,log)$

Kaveh

@KristofferArnsfeltHansen: Es ist schon eine Weile her, dass Sie dies beantwortet haben, aber haben Sie eine Referenz, bei der die Gleichwertigkeit zwischen der Schaltung und den TM-Definitionen von L bewiesen ist?

Robin Kothari

@ Robin, daran kann ich eigentlich nicht denken. Vielleicht weiß Vinay es?

Kristoffer Arnsfelt Hansen

Schauen Sie sich dieses Papier von McKenzie, Reinhardt, Vinay an . Wir verwenden Multiplex-Auswahlgatter, um Klassen zwischen und zu charakterisieren , einschließlich , usw. Zum Beispiel ist $NC^1$ $LOGCFL$ $L$ $LOGDCFL$ $L = MWidth, Size(log,poly).$

$NL$ $NL$

V Vinay
quelle