P-Completeness and Parallel Computation

Problem Detail: 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?

Asked By : Dave Clarke

Answered By : Massimo Cafaro

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

  1. $POLYLOGSPACE ⊄ P$
  2. $P ⊄ POLYLOGSPACE$

$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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1415

Leave a Reply