14
$\begingroup$

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}$?

$\endgroup$
  • 1
    $\begingroup$ Also, note this similar question. $\endgroup$ – Nicholas Mancuso Sep 24 '12 at 16:20
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the 2 references and the partial answer. The Limits to Parallel Computation book does a better job than the other books I've looked at, but is still relatively old and not quite as thorough as I'd like. $\endgroup$ – Mike Izbicki Sep 24 '12 at 15:36
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.