Mogą

Pozwolić $\mathsf{ATISP}(f(n), g(n))$ być klasą języków ustaloną przez naprzemienne maszyny Turinga, które zatrzymują się w czasie $f(n)$ używając przestrzeni $g(n)$. Pozwolić$\mathsf{AALTSP}(f(n), g(n))$ być klasą języków ustaloną przez naprzemienne używanie maszyn Turinga $f(n)$ alternacje i przestrzeń $g(n)$.

Ruzzo udowodnił , że$\mathsf{NC}^k = \mathsf{ATISP}(\log^k n, \log n)$. On też to pokazał$\mathsf{NC}^k \subseteq \mathsf{AALTSP}(\log^k n, \log n) \subseteq \mathsf{NC}^{k + 1}$.

Jest $\mathsf{NC}^k = \mathsf{AALTSP}(\log^k n, \log n)$?

Oczywiście równości i inkluzje przedstawione w pytaniu dotyczą wyłącznie munduru $\mathsf{NC}^k$. Klasa$\mathsf{AALTSP}(\log^k n, \log n)$ jest taki sam jak mundur $\mathsf{AC}^k$, więc pytanie jest takie samo, jak $\mathsf{NC}^k = \mathsf{AC}^k$.

W szczególności sprawa $k=1$ implikuje to $\mathsf{L}$ jest równe $\mathsf{NL}$ i nawet $\mathsf{LogCFL}$, od $\mathsf{NC}^1 \subseteq \mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{LogCFL} \subseteq \mathsf{AC}^1$.