<p>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 <a href="http://www.sciencedirect.com/science/article/pii/089054019190017V">Mix Barrington and McKenzie</a> ask the question of whether $\mathsf{NSC}^2$ is closed under complement.</p>

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

CC BY-SA 3.0
2017-01-30T11:17:16.630Z
I don't think there has been.  I guess that Ryan Williams would know, so we should wait for him to chime in, but both authors that you mention are not on cstheory.SE; you may try contacting them if this becomes inconclusive.
Michaël Cadilhac
CC BY-SA 4.0
2023-10-19T15:54:30.527Z
It is not known whether NSC is closed under complement.  I would conjecture that it's not -- but this isn't based on much.  I've written two papers that deal with NSC, and I regret that neither of them cites [Barrington, McKenzie].  They are:  http://dx.doi.org/10.4086/cjtcs.2013.005 and http://dx.doi.org/10.4086/toc.2014.v010a012  There aren't many other papers of which I'm aware that deal with NSC.  The three of which I am aware are: https://doi.org/10.1145/3154856 https://doi.org/10.1145/3188745.3188924 and https://eprint.iacr.org/2017/1250.pdf
Eric Allender
CC BY-SA 4.0
2023-10-19T16:01:11.410Z
Oops: One more: https://eprint.iacr.org/2017/1250.pdf
Eric Allender
<cc.complexity-theory><complexity-classes>
Is the class NSC closed under complement?
funnyhow0x3f
# Is the class NSC closed under complement?

(Asked by: username_0 on 2017-01-30)

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](http://www.sciencedirect.com/science/article/pii/089054019190017V) 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$?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: I don't think there has been.  I guess that Ryan Williams would know, so we should wait for him to chime in, but both authors that you mention are not on cstheory.SE; you may try contacting them if this becomes inconclusive.  
> **username_2**: It is not known whether NSC is closed under complement.  I would conjecture that it's not -- but this isn't based on much.  I've written two papers that deal with NSC, and I regret that neither of them cites [Barrington, McKenzie].  They are:  http://dx.doi.org/10.4086/cjtcs.2013.005 and http://dx.doi.org/10.4086/toc.2014.v010a012  There aren't many other papers of which I'm aware that deal with NSC.  The three of which I am aware are: https://doi.org/10.1145/3154856 https://doi.org/10.1145/3188745.3188924 and https://eprint.iacr.org/2017/1250.pdf  
> **username_2**: Oops: One more: https://eprint.iacr.org/2017/1250.pdf  

---

## 0 answers

