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

From the ArXiv: http://arxiv.org/abs/0907.3965

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.