computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

, the parallel computation thesis is a

hypothesis A hypothesis (plural hypotheses) is a proposed explanation for a phenomenon. For a hypothesis to be a scientific hypothesis, the scientific method requires that one can testable, test it. Scientists generally base scientific hypotheses on prev ...

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 Chandra ( sa, चन्द्र, Candra, shining' or 'moon), also known as Soma ( sa, सोम), is the Hindu god of the Moon, and is associated with the night, plants and vegetation. He is one of the Navagraha (nine planets of Hinduism) a ...

and Stockmeyer in 1976. In other words, for a

computational model A computational model uses computer programs to simulate and study complex systems using an algorithmic or mechanistic approach and is widely used in a diverse range of fields spanning from physics, chemistry and biology to economics, psychology, ...

which allows computations to branch and run in parallel without bound, a

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of s ...

which is decidable under the model using no more than

t(n)

steps for inputs of length ''n'' is decidable by a non-branching machine using no more than

t(n)^k

units of storage for some constant ''k''. Similarly, if a machine in the unbranching model decides a language using no more than

s(n)

storage, a machine in the parallel model can decide the language in no more than

s(n)^k

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 A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algor ...

non-deterministic Turing machine In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...

, and

alternating Turing machine In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) 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) introduced a model for which the thesis does not hold. However, the model allows

2^

parallel threads of computation after

T(n)

steps. (See Big O notation.) Parberry (1986) suggested a more "reasonable" bound would be

2^

2^

, in defense of the thesis. Goldschlager (1982) 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.

References

{{reflist Parallel computing Theory of computation