Parallel computation thesis
Encyclopedia
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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the parallel computation thesis is a hypothesis
Hypothesis
A hypothesis is a proposed explanation for a phenomenon. The term derives from the Greek, ὑποτιθέναι – hypotithenai meaning "to put under" or "to suppose". For a hypothesis to be put forward as a scientific hypothesis, the scientific method requires that one can test it...
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
Larry Stockmeyer
Larry Joseph Stockmeyer was a computer scientist. He was one of the pioneers in the field of computational complexity theory, and he also worked in the field of distributed computing...
in 1976 (see References).
In other words, for a computational model
Computational model
A computational model is a mathematical model in computational science that requires extensive computational resources to study the behavior of a complex system by computer simulation. The system under study is often a complex nonlinear system for which simple, intuitive analytical solutions are...
which allows computations to branch and run in parallel without bound, a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
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
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
, non-deterministic Turing machine
Non-deterministic Turing machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers....
, and alternating Turing machine
Alternating Turing machine
In computational complexity theory, an alternating Turing machine is a non-deterministic Turing machine with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP...
. 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 notationBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
.) 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.