You are currently browsing the tag archive for the ‘NC’ tag.

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.