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.

NC is Nick's Class (named after Nick Pippenger) and can be characterized by either a PRAM model with polynomial processors and poly-logarithmic time or by polylogarithmic-depth polynomial-sized circuits^{1}.

So what about nondeterministic NC or NNC? NNC is just the same as NP.

First let's consider randomized NC, RNC. Here each processors each had a limited number of random bits but they can share their random bits through memory, a technique used for example to find maximal matchings.

NNC, particularly if you want to have RNC ⊆ NNC, needs to have a similar definition. Suppose all the processors could act nondeterministically. Here is an NNC algorithm for 3SAT with n variables and m clauses.

- Processor i (1 ≤ i ≤ n) guesses the ith bit of a potential satisfying assignment and writes it in memory location i.
- Processor j (1 ≤ j ≤ m) checks whether this assignment makes clause j true.
- If all processors in the second round accept than accept (which takes another log m rounds).

Since 3SAT is NP-complete under reductions computable easily in parallel, we have NNC = NP. The reverse direction is a simple simulation.

A simple observation but a very important point: Every nondeterministic computation has an easy nondeterministic parallelization.

Alternately you can define RNC or NNC with an additional random or nondeterministic input (in either the circuit or parallel model) and get the same classes.

RL and NL on the other hand handle randomness and nondeterministic differently. Here you have one processor using polynomial time and logarithmic space. While the processor can use a polynomial number of random/nondeterministic bits, the processor cannot remember them all. So RL and NL are considerably weaker, in particular both are contained in P.

- I'm ignoring uniformity issues in this post.

--

Posted By Lance to Computational Complexity at 6/18/2009 09:38:00 AM