6
$\begingroup$

The class $\mathsf{NSC}$ is defined as $\bigcup_{k\in\mathbb{N}}\mathsf{NSC}^k$, where $\mathsf{NSC}^k = \mathsf{NTIMESPACE}[\mathsf{poly},\mathsf{log}^k]$. In a 1991 paper Mix Barrington and McKenzie ask the question of whether $\mathsf{NSC}^2$ is closed under complement.

Has there been any progress on that question for $\mathsf{NSC}$ in general or for particular values of $k$?

Improve this question
$\endgroup$
3

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.