Czy L ma definicję obwodów?

Wiele klas złożoności zdefiniowanych za pomocą maszyn Turinga ma definicje w kategoriach jednorodnych obwodów. Na przykład P można również zdefiniować za pomocą obwodów o jednorodnych rozmiarach wielomianowych, podobnie BPP, NP, BQP itp. Można zdefiniować za pomocą obwodów jednorodnych.

Czy istnieje oparta na obwodzie definicja L?

Oczywistym pomysłem byłoby dopuszczenie obwodów wielomianowych z pewnymi ograniczeniami głębokości, ale okazało się, że definiuje hierarchię NC.

Już dawno myślałem o tym pytaniu, ale nie znalazłem odpowiedzi. Jeśli dobrze pamiętam, moją motywacją było zrozumienie, jak wyglądałby kwantowy analog L.

cc.complexity-theory complexity-classes circuit-complexity Robin Kothari
źródło

Czy obwody logarytmiczne zawierają

L

$L$

Mohammad Al-Turkistany,

@Turkistany: Nie, nie sądzę, ponieważ obwód wielkości kłody może mieć co najwyżej głębokość kłody, a zatem jest zawarty w NC_1, która jest zdefiniowana jako głębokość kłody, obwody wielkości wielorakich. NC_1 jest zawarty w L i nie wiadomo, że jest równy L.

Robin Kothari

Odpowiedzi:

$L = SC^1$ $SC^1$ $O(\log n)$

$NL$

Kristoffer Arnsfelt Hansen
źródło

Potrzebujemy, aby obwody były jednolite, prawda?

Hsien-Chih Chang 之之

Prawidłowo, powinny być jednolite.

Kristoffer Arnsfelt Hansen

S C^{1}

$SC^1$

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

$DTimeSpace(poly,log)$

@KristofferArnsfeltHansen: Minęło trochę czasu, odkąd odpowiedziałeś na to pytanie, ale czy masz referencję, w której udowodniono równoważność definicji L i obwodu?

Robin Kothari,

@ Robin, właściwie nie mogę o tym myśleć. Może Vinay wie?

Kristoffer Arnsfelt Hansen

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

$NL$ $NL$

V Vinay
źródło