Машинная характеристика

$SAC^i$ - это класс задач решения, разрешимых семейством схем глубины с вентилями ИЛИ без ограничений и с вентилями И с ограниченными вентиляторами. Отрицания допускаются только на входном уровне. Известно, что для замкнуто относительно дополнения, а - нет. Кроме того, и, следовательно, имеет машинную характеристику, поскольку LogCFL - это набор языков, принимаемых ограниченным пространственным и ограниченным полиномиальным временем вспомогательным КПК. Существуют ли похожие машинные характеристики для ? $O({\log}^i{n})$ $SAC^i$ $i \geq 1$ $SAC^0$ $SAC^1 = LogCFL$ $O({\log}n)$ $SAC^i$ $i \geq 2$

cc.complexity-theory circuit-complexity space-bounded arithmetic-circuits Шива Кинтали
источник

А и имел в виду, что то же самое?

k

$k$

i

$i$

Андрас Саламон

Да. Извините за опечатку. Исправлено сейчас.

Шива Кинтали

Ответы:

Да. Высота стека , то есть, с пространство и высоту стопки; это подразумевает конфигураций и, следовательно, битов. У нас есть $\mathsf{SAC^1} = \mathsf{NAuxPDA}(\log n, \log n)$ $O(\log n)$ $O(\log n)$ $\log n$ $\log^2(n)$

S A C^{k} = N A u x P D A (\log n, \log^{k} n);

$\mathsf{SAC^k} = \mathsf{NAuxPDA}(\log n, \log^k n);$

эти машины будут работать за время . Без ограничения высоты стека мы получим точно . Результат должен следовать из: W. Ruzzo, Ограничение размера дерева. ССПС 1980. $2^{\log^{k}(n)}$ $\mathsf{P}$

V Vinay
источник

Vinay, вы можете использовать обычный латекс в ответе: это может помочь сделать его немного более читабельным

Suresh Venkat