L a-t-il une définition en termes de circuits?

De nombreuses classes de complexité définies avec les machines de Turing ont des définitions en termes de circuits uniformes. Par exemple, P peut également être défini en utilisant des circuits de taille polynomiale uniforme, et de même BPP, NP, BQP, etc. peuvent être définis avec des circuits uniformes.

Existe-t-il donc une définition de L basée sur les circuits?

Une idée évidente serait de permettre des circuits de taille polynomiale avec une certaine limitation de profondeur, mais cela s'avère définir la hiérarchie NC.

Je pensais à cette question il y a longtemps, mais je n'ai pas trouvé de réponse. Si je me souviens bien, ma motivation était de comprendre à quoi ressemblerait l'analogue quantique de L.

cc.complexity-theory complexity-classes circuit-complexity Robin Kothari
la source

Les circuits de taille logarithmique contiennent-ils du

L

$L$

Mohammad Al-Turkistany

@Turkistany: Non, je ne pense pas, car un circuit de taille de journal peut tout au plus avoir une profondeur de journal, et est donc contenu dans NC_1, qui est défini comme une profondeur de journal, des circuits de taille poly. NC_1 est contenu dans L, et n'est pas connu pour être égal à L.

Robin Kothari

Réponses:

Eh bien, , où est la classe de langages calculée par des circuits de taille polynomiale de largeur . $L = SC^1$ $SC^1$ $O(\log n)$

Quant à , il pourrait être caractérisé comme les langages de classe calculés par des circuits asymétriques de taille polynomiale (ce qui, dans un certain sens, n'est qu'une autre façon de dire des programmes de branchement non déterministes). $NL$

Kristoffer Arnsfelt Hansen
la source

Nous avons besoin que les circuits soient uniformes, non?

Hsien-Chih Chang 張顯之

Exact, ils devraient être uniformes.

Kristoffer Arnsfelt Hansen

S C^{1}

$SC^1$ est défini à l'aide de machines de Turing comme

, il est donc déjà uniforme.

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

$DTimeSpace(poly,log)$

Kaveh

@KristofferArnsfeltHansen: Cela fait un moment que vous n'avez pas répondu, mais avez-vous une référence où l'équivalence entre le circuit et les définitions TM de L est prouvée?

Robin Kothari

@Robin, je ne peux pas y penser, en fait. Peut-être que Vinay le sait?

Kristoffer Arnsfelt Hansen

$NC^1$ $LOGCFL$ $L$ $LOGDCFL$ $L = MWidth, Size(log,poly).$

$NL$ a une caractérisation naturelle basée sur des circuits utilisant des circuits asymétriques. Ceci est juste une représentation en circuit du programme de branchement qui représente $NL$ . Les circuits obliques sont dus à Venkateswaran.

V Vinay
la source