Content deleted Content added
Dialectric (talk | contribs) →References: add Category:Parallel computing |
m link Stockmeyer |
||
Line 1:
In [[computational complexity theory]], the '''parallel computation thesis''' is a [[hypothesis]] which states that the time used by a (reasonable) parallel machine is polynomially related to the space used by a sequential machine. The parallel computation thesis was set forth by Chandra and [[Larry Stockmeyer|Stockmeyer]] in 1976 (see References).
In other words, for a [[computational model]] which allows computations to branch and run in parallel without bound, a [[formal language]] which is [[decidable language|decidable]] under the model using no more than <math>t(n)</math> steps for inputs of length ''n'' is decidable by a machine in the unbranching model using no more than <math>t(n)^k</math> units of storage for some constant ''k''. Similarly, if a machine in the unbranching model decides a language using no more than <math>s(n)</math> storage, a machine in the parallel model can decide the language in no more than <math>s(n)^k</math> steps for some constant ''k''.
| |||