У L есть определение в терминах цепей?

Многие классы сложности, определенные с помощью машин Тьюринга, имеют определения в терминах однородных цепей. Например, P также может быть определен с использованием схем с однородным полиномиальным размером, и аналогично BPP, NP, BQP и т. Д. Могут быть определены с помощью однородных схем.

Так есть ли основанное на схеме определение L?

Очевидная идея состояла бы в том, чтобы разрешить схемы полиномиального размера с некоторым ограничением глубины, но это, как оказалось, определяет иерархию ЧПУ.

Я думал об этом вопросе давным-давно, но не нашел ответа. Если я правильно помню, моей мотивацией было понять, как будет выглядеть квантовый аналог L.

cc.complexity-theory complexity-classes circuit-complexity Робин Котари
источник

Схемы логарифмического размера содержат

L

$L$

Мухаммед Аль-Туркистани

@Turkistany: Нет, я так не думаю, так как схема размера журнала может иметь максимальную глубину записи и, таким образом, содержится в NC_1, который определяется как глубина журнала, схемы разного размера. NC_1 содержится в L и неизвестно, что он равен L.

Робин Котари

Ответы:

Ну, , где - это класс языков, рассчитанный по схемам полиномиального размера шириной . $L = SC^1$ $SC^1$ $O(\log n)$

Что касается , его можно охарактеризовать как языки классов, вычисленные с помощью асимметричных схем полиномиального размера (что в некотором смысле является еще одним способом обозначения недетерминированных программ ветвления). $NL$

Кристоффер Арнсфельт Хансен
источник

Нам нужно, чтобы цепи были одинаковыми, верно?

Сянь-Чи Чанг 之之

Правильно, они должны быть одинаковыми.

Кристоффер Арнсфельт Хансен

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: Прошло много времени с тех пор, как вы ответили на это, но есть ли у вас ссылка, где доказана эквивалентность между схемой и определениями ТМ L?

Робин Котари

@ Робин, я не могу думать об этом, на самом деле. Возможно, Виная знает?

Кристоффер Арнсфельт Хансен

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

$NL$ $NL$

V Vinay
источник