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 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 under the model using no more than steps for inputs of length n is decidable by a machine in the unbranching model using no more than units of storage for some constant k. Similarly, if a machine in the unbranching model decides a language using no more than storage, a machine in the parallel model can decide the language in no more than steps for some constant k.
The parallel computation thesis is not a rigorous formal statement, as it does not clearly define what constitutes an acceptable parallel model. A parallel machine must be sufficiently powerful to emulate the sequential machine in time polynomially related to the sequential space; compare Turing machine, non-deterministic Turing machine, and alternating Turing machine. N. Blum (1983) has introduced a model for which the thesis does not hold. However, the model allows parallel threads of computation after steps. (See Big O notation.) Parberry (1986) suggested a more "reasonable" bound would be or, in defense of the thesis. Goldschlager (1982) has proposed a model which is sufficiently universal to emulate all "reasonable" parallel models, which adheres to the thesis. Chandra and Stockmeyer originally formalized and proved results related to the thesis for deterministic and alternating Turing machines, which is where the thesis originated.
Famous quotes containing the words parallel, computation and/or thesis:
“One writes of scars healed, a loose parallel to the pathology of the skin, but there is no such thing in the life of an individual. There are open wounds, shrunk sometimes to the size of a pin-prick but wounds still. The marks of suffering are more comparable to the loss of a finger, or the sight of an eye. We may not miss them, either, for one minute in a year, but if we should there is nothing to be done about it.”
—F. Scott Fitzgerald (1896–1940)
“I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...”
—Minnie Maddern Fiske (1865–1932)
“Some have said that the thesis [of indeterminacy] is a consequence of my behaviorism. Some have said that it is a reductio ad absurdum of my behaviorism. I disagree with this second point, but I agree with the first. I hold further that the behaviorism approach is mandatory. In psychology one may or may not be a behaviorist, but in linguistics one has no choice.”
—Willard Van Orman Quine (b. 1908)