Charakterystyka maszynowa

O ( log i n ) S A C i i ≥ 1 S A C 0 S A C 1 = L o g C F $SAC^i$ jest klasą problemów decyzyjnych rozwiązanych przez rodzinę obwodów głębinowych z nieograniczoną liczbą Fanin OR i ograniczonymi bramkami Fanin AND. Negacje są dozwolone tylko na poziomie wejściowym. Wiadomo, że dla jest zamknięty pod uzupełnieniem, a nie. Ponadto a zatem ma charakterystykę maszynową, ponieważ LogCFL jest zestawem języków akceptowanych przez ograniczoną przestrzenią i wielomianowy pomocniczy PDA. Czy istnieją podobne charakterystyki maszynowe dla ?$O({\log}^i{n})$$SAC^i$$i \geq 1$$SAC^0$$SAC^1 = LogCFL$S A C i i ≥ $O({\log}n)$$SAC^i$$i \geq 2$

Tak. Wysokość stosu. , to jest z O ( log n ) miejsca i O ( log n ) wysokość stosu; oznacza to konfiguracje log n, a zatem log 2 ( n ) bitów. Mamy$\mathsf{SAC^1} = \mathsf{NAuxPDA}(\log n, \log n)$$O(\log n)$$O(\log n)$$\log n$$\log^2(n)$

maszyny te będą działać w czasie . Bez ograniczenia wysokości stosu, będziemy mieli dokładnie P . Wynik powinien wynikać z: W. Ruzzo, Alternacja wielkości drzewa. JCSS 1980.$2^{\log^{k}(n)}$$\mathsf{P}$