L tem uma definição em termos de circuitos?

Muitas classes de complexidade definidas com máquinas de Turing têm definições em termos de circuitos uniformes. Por exemplo, P também pode ser definido usando circuitos de tamanho polinomial uniforme, e similarmente BPP, NP, BQP, etc. podem ser definidos com circuitos uniformes.

Então, existe uma definição baseada em circuito de L?

Uma idéia óbvia seria permitir circuitos de tamanho polinomial com alguma limitação de profundidade, mas isso acaba por definir a hierarquia do NC.

Eu estava pensando nessa pergunta há muito tempo, mas não encontrei uma resposta. Se bem me lembro, minha motivação era entender como seria o análogo quântico de L.

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

Os circuitos logarítmicos contêm ?

L

$L$

Mohammad Al-Turkistany

@Turkistany: Não, acho que não, já que um circuito de tamanho de registro pode ter no máximo profundidade de registro e, portanto, está contido em NC_1, que é definido como profundidade de registro, circuitos de tamanho poli. NC_1 está contido em L e não é conhecido como igual a L.

Robin Kothari

Respostas:

Bem, , onde é a classe de idiomas calculada por circuitos de tamanho polinomial de largura . $L = SC^1$ $SC^1$ $O(\log n)$

Quanto , poderia ser caracterizada como as línguas de classe calculadas pelo tamanho polinomial inclinação circuitos (que em certo sentido é apenas outra maneira de dizer programas de ramificação nondeterministic). $NL$

Kristoffer Arnsfelt Hansen
fonte

Precisamos que os circuitos sejam uniformes, certo?

Hsien-Chih Chang,

Correto, eles devem ser uniformes.

Kristoffer Arnsfelt Hansen

S C^{1}

$SC^1$ está definido usando Turing Máquinas como

por isso é já uniforme.

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

$DTimeSpace(poly,log)$

Kaveh

@KristofferArnsfeltHansen: Já faz um tempo desde que você respondeu isso, mas você tem uma referência em que a equivalência entre o circuito e as definições de MT de L é provada?

precisa

@ Robin, não consigo pensar nisso, na verdade. Talvez Vinay saiba?

Kristoffer Arnsfelt Hansen,

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

$NL$ $NL$

V Vinay
fonte