You are currently browsing John Moeller’s articles.

From the ArXiv:


Lance Fortnow has a new blog post about “Nondeterministic NC.” He responds to a reader question:

Can we define a class NNC such that NC ⊆ RNC ⊆ NNC. Is NNC known by some other name? It is clear that NNC ⊆ NP, but the reverse is not obvious.

We are not meeting tomorrow (Thursday), as Suresh is still ill with a mystery bug. We will reconvene Monday (June 22). I have updated the Wiki.