Some questions on parallel computing and the class NC

Question

I have a number of related questions about these two topics.

First, most complexity texts only gloss over the class $\mathbb{NC}$. Is there a good resource that covers the research more in depth? For example, something that discusses all of my questions below. Also, I'm assuming that $\mathbb{NC}$ still sees a fair amount of research due to its link to parallelization, but I could be wrong. The section in the complexity zoo isn't much help.

Second, computation over a semigroup is in $\mathbb{NC}^1$ if we assume the semigroup operation takes constant time. But what if the operation does not take constant time, as is the case for unbounded integers? Are there any known $\mathbb{NC}^i$-complete problems?

Third, since $\mathbb{L} \subseteq \mathbb{NC}^2$, is there an algorithm to convert any logspace algorithm into a parallel version?

Fourth, it sounds like most people assume that $\mathbb{NC} \ne \mathbb{P}$ in the same way that $\mathbb{P} \ne \mathbb{NP}$. What is the intuition behind this?

Fifth, every text I've read mentions the class $\mathbb{RNC}$ but gives no examples of problems it contains. Are there any?

Finally, this answer mentions problems in $\mathbb{P}$ with sublinear parallel execution time. What are some examples of these problems? Are there other complexity classes that contain parallel algorithms that are not known to be in $\mathbb{NC}$?

Answer 1

Third, since $\sf{L} \subseteq \sf{NC}^2$, is there an algorithm to convert any logspace algorithm into a parallel version?

It can be shown (Arora and Barak textbook) given a $t(n)$-time TM $M$, that an oblivious TM $M'$ (i.e. a TM whose head movement is independent of its input $x$) can construct a circuit $C_n$ to compute $M(x)$ where $|x| = n$.

The proof sketch is along the lines of having $M'$ simulate $M$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $t_i$ (think of a computational log). Each step $t_i$ can be computed from $x$ and the state $t_{i-1}$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $t_i$ can be computed by a constant-sized circuit.

If you compose the constant-sized circuits for each $t_i$ we have a circuit that computes $M(x)$. Using this fact, along with the restriction that the language of $M$ is in $\sf{L}$ we see that our circuit $C_n$ is by definition logspace-uniform, where uniformity just means that our circuits in our circuit family $\{C_n\}$ computing $M(x)$ all have the same algorithm. Not a custom-made algorithm for each circuit operating on input size $n$.

Again, from the definition of uniformity we see that circuits deciding any language in $\sf{L}$ must have a function $\text{size}(n)$ computable in $O(\log n).$ The circuit family $\sf{AC}^1$ has at most $O(\log n)$ depth.

Finally it can be shown that $\sf{AC}^1 \subseteq \sf{NC}^2$ giving the relation in question.

Fourth, it sounds like most people assume that $\sf{NC} \neq \sf{P}$ in the same way that $\sf{P} \neq \sf{NP}$. What is the intuition behind this?

Before we go further, let us define what $\sf{P}$-completeness means.

A language $L$ is $\sf{P}$-complete if $L \in \sf{P}$ and every language in $\sf{P}$ is logspace reducible to it. Additionally, if $L$ is $\sf{P}$-complete then the following are true

1. $L \in \sf{NC} \iff \sf{P} = \sf{NC}$

2. $L \in \sf{L} \iff \sf{P} = \sf{L}$

Now we consider $\sf{NC}$ to be the class of languages efficiently decided by a parallel computer (our circuit). There are some problems in $\sf{P}$ that seem to resist any attempt at parallelization (i.e. Linear Programming, and Circuit Value Problem). That is to say, certain problems require computation to be done in a step-wise fashion.

For example, the Circuit Value Problem is defined as:

Given a circuit $C$, input $x$, and a gate $g \in C$, what is the output of $g$ on $C(x)$?

We do not know how to compute this any better than computing all the gates $g'$ that come before $g$. Given some of them may be computed in parallel, for example if they all occur at some time-step $t_i$, but we dont know how compute the output of gates at timestep $t_i$ and time-step $t_{i+1}$ for the obvious difficulty that gates at $t_{i+1}$ require the output of gates at $t_i$!

This is the intuition behind $\sf{NC} \neq \sf{P}$.

---

Limits to Parallel Computation is a book about $\sf{P}$-Completeness in similar vein of Garey & Johnson's $\sf{NP}$-Completeness book.

Answer 2

Fifth, every text I've read mentions the class RNC but gives no examples of problems it contains. Are there any?

The paper "Matching is as Easy as Matrix Inversion" by Mulmuley, Vazirani, and Vazirani has several examples of problems in class $\mathbb{RNC}^2$. The main one is finding a maximal matching, then they reduce other problems to this one.