Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I was recently reading about algorithms for checking bisimilarity and read that the problem is P-complete. Furthermore, a consequence of this is that this problem, or any P-complete problem, is unlikely to have an efficient parallel algorithms.
What is the intuition behind this last statement?
Any $P$-complete problem, is unlikely to have an efficient parallel algorithm. Why ?
The existence of $P$-complete problems is the most important clue that $(P ∩ POLYLOGSPACE) ≠ P$. The question then is, why is this conjecture relevant to parallel computing? Let's start with the resources used in a computation. For sequential computing: time and space; for parallel computing: time and hardware (number of processors). Is there a relation? Yes! Sequential space ↔ parallel time; Sequential time ↔ parallel hardware. The correspondence between sequential space and parallel time seems to be independent from the parallel computing model adopted; this leads to the following, so called parallel computation thesis which is unproven.
(Chandra and Stockmeyer) Every computation of a TM with space complexity $S(n)$ can be simulated in a parallel computing model in time $T(n) = O(S(n)^{O(1)})$ and every computation of a parallel computing model with time complexity $T’(n)$ can be simulated by a TM with space complexity $S’(n) = O(T’(n)^{O(1)})$.
The class of problems solvable sequentially in polynomial space is $PSPACE$ and the set of problems solvable in polynomial time is $P$.Since $PSPACE$ is thought to be a much larger class of problems than $P$, the thesis quantifies the effective improvement made possible by parallelism. A consequence of this thesis is that a PRAM can solve $NP$-complete problems in polynomial time… Unfortunately, no! The parallel computation thesis implies that we can actually deal with problems belonging to $PSPACE$… but this requires an exponential number of processors! A time-space trade-off is working: The exponential time on the sequential computing model is transformed into an exponential number of processors on the parallel computing model, whereas the polynomial space on the sequential computing model is transformed into a polynomial time on the parallel computing model.
This trade-off is easier to understand if we try to restrict both parallel time and parallel hardware: if the parallel computing model has a polynomial number of processors, then the class of problems solvable in parallel polynomial time is $P$. If we restrict the number of processors to a polynomial we can improve the performances of a sequential machine, but no more than a polynomial factor. Thus we can reduce the degree of the polynomial representing the time complexity, but we are not able using parallelism to reduce exponential costs to polynomial costs.
The problems solved in parallel with polynomial time complexity are those problems belonging to $P$. The polynomial constraint on the number of processors leads to a parallel computing model equivalent to TM. There are two important practical considerations: which polynomial number of processors is acceptable/affordable ? In practice, the polynomial number of processors is meant to be linear or close. Which subpolynomial time is achievable ? It turned out that almost all highly parallel feasible problems can achieve polylogarithmic parallel time. In parallel, a time complexity which is logarithmic in the input length represents an efficient parallel computation. A parallel algorithm is considered efficient if, given a polynomial number of processors, its time complexity is polylogarithmic.
Given a problem $R \in TIME\_SPACE_{TM}(n^k, (log n)^h)$ where $k$ and $h$ are constants, the parallel computation thesis implies the existence of a parallel algorithm for $R$ with time complexity $O((log n)^{k’})$ where $k’$ is a constant. The comparison between sequential and parallel time allows classifying $R$ as a problem highly parallelizable (from a time perspective).
From the parallel computation thesis, it follows that $POLYLOGSPACE$ is the class of problems highly parallelizable. $POLYLOGSPACE$ does not contain problems complete with regard to log-space reductions; this implies $POLYLOGSPACE \neq P$. It seems that
$P ∩ POLYLOGSPACE$ contains the problems that can be solved in polynomial time using polylogarithmic space. $P$-complete problems probably belongs to $P - (P ∩ POLYLOGSPACE)$.
$NC$ (Nick’s class - so called in honour of Nicholas Pippenger, the first to identify and to characterize it in 1979) is the class of problems that can be solved in polylogarithmic time (i.e., with time complexity $O((log n)^k))$ with a polynomial number of processors (I.e., bounded by $O(f(n))$ for some polynomial function $f$ where $n$ is the problem size) The parallel computation thesis implies $NC ⊂ (P ∩ POLYLOGSPACE)$.
However, unfortunately by definition $NC$ also includes lots of problems which are not efficiently parallelizable. The most infamous example is parallel binary search. The trouble is that this problem has polylogarithmic time complexity even for $p$ = 1. Any sequential algorithm requiring at most logarithmic time in the worst case is in $NC$ regardless of its parallel feasibility!
Now, we can finally explain why $P$-complete problems are the hardest parallelizable problems. Given a $P$-complete problem $Q$, it is very unlikely the existence of an efficient parallel algorithm: if such a parallel algorithm would exist with time complexity $O((log n)^k)$, then the parallel computation thesis will imply the existence of a sequential algorithm with space complexity $O((log n)^{k’})$ for the same problem. Since $Q$ is a $P$-complete problem this in turn will imply that every problem in $P$ can be solved in poly-log space: $(P ∩ POLYLOGSPACE) = P$. As you already know, we instead believe that $(P ∩ POLYLOGSPACE) ⊂ P$, even though we are not yet able to prove this.
One final observation, about the polynomial processor requirement. Well, that is a theoretical statement. In practice: a processor requirement that grows faster than the problem size might not really be useful.
Because "efficient parallel" falls inside $\mathsf{NC}$ (“Nick's Class” of problems decidable in polylogarithmic time with a polynomial number of processors), and it is widely believed that $\mathsf{NC} \neq \mathsf{P}$. So any $\mathsf{P\text{-}complete}$ problem is not believed to have an efficient parallel algorithm (since that would imply that $\mathsf{P} = \mathsf{NC}$).
Of course all of this is up to conjecture that $\mathsf{NC} \neq \mathsf{P}$, as you know it is an open problem that $\mathsf{P}$ is not in the first level of $\mathsf{NC}$, i.e. we don't know if $\mathsf{NC^1} \neq \mathsf{P}$.
Even more, we don't even know if you cannot solve problems in $\mathsf{P}$ in $\mathsf{AC^0[6]}$, i.e. constant depth (=constant parallel time) boolean circuits with $\mod_6$ gates.
For further information, take a look at the following book:
Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo, "Limits to Parallel Computation: P-Completeness Theory", 1995.
Kaveh's answer covers the usual definition of "parallelism", which is NC. The question of whether P $<$ NC is one of the harder questions in complexity theory (and in some ways just as relevant as the P $<$ NP question).
The intuition behind it is that some problems in P, like linear programming, or DFS order feel like they have a lot of dependencies that force a long "critical path" that can't be parallelized. This is not a proof any more than non-determinism seeming to be very powerful is, but this is the basic idea.
Edit: To clarify for the comments, the point of this answer is to say why (some) people don't think that P and NC are the same. Much as with P and NP, nobody knows how to prove whether the two are different, but there is something about the hard problems that makes (some) computer scientists think they are.
Another aside is that NC is "polylog time on polynomially many processors", which is asking for a very dramatic speedup but giving a lot of processors. Thus it might not fit a practical notion of parallelizable.
In particular, if you think that P $<$ NP, then you will start looking at heuristics and approximation algorithms right away for NP-complete problems. On the other hand, even if you think that NC is smaller than P, you might be able to get non-trivial speedups from the kinds of parallelism available from today's computers.
Be very mindful of who takes "efficient parallel algorithms" to mean what, exactly.
The older answers explain the perspective of complexity theory. There, "efficient" usually means something vague like "runtime in $O(f(n))$ time with $O(g(n))$ processors". Note that the number of processors can depend on the input size!
In particular, the often named class NC is the
set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors.
This has nothing to do with whether there are parallel algorithms for these problems which are efficient in more practical terms¹:
Just because there is no NC algorithm for a problem does not mean there isn't a "real" one; just because we can not break apart the problem into polynomially many very small pieces does not mean we can not break it into constantly many sufficiently smaller ones, as $n$ grows.
For instance, on constantly many processors with shared memory, CYK parsing can be done in parallel with asymptotically optimal speedup (see my master thesis, even though context-free parsing is P-complete.
Describing efficiency on machines with finitely many processors in a useful way requires more precise analysis than $O(\dots)$ since speed-up is bounded by a finite constant, the number of processors². You rarely find this in complexity theory. Therefore, if you want to learn about parallel algorithms that are of use in the real world, I would advise to look elsewhere.
Let $T_p : \mathbb{N} \to \mathbb{R_{\geq 0}}$ the runtime function of a parallel algorithm. You might want to call an algorithm "efficient" if $T_1(n)/T_p(n) \approx p$, or if $T_1(n) \approx T(n)$ for $T$ the runtime function of a good sequential algorithm. I propose this in a more rigorous fashion in my master thesis, building from literature cited therein.
This is not always true; memory hierarchy and hardware may allow for larger speedup, at least sometimes. There will be another constant bound, though.
Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?
That question was marked as duplicate this question, so let me just assume that it is really a duplicate, and provide one possible answer.
We know that NC != PSPACE, hence a proof that P=NC would also prove P != PSPACE. That may not sound like a big deal, but it is one consequence for computer science research.
Why do we know NC != PSPACE? Well, we know NCk ⊆ DSPACE(O(logk)), so we can just use the space hierarchy theorem.
In term of practical applications, the applications around linear (and convex) programming might be so seducing that custom parallel architectures together with compilers for translating linear programming formulations efficiently to that hardware could be developed and sold.
