Parallel computation thesis: Difference between revisions

Revision as of 19:20, 14 February 2011

Revision as of 19:21, 14 February 2011

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