Parallel computation thesis

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.

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 $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, non-deterministic Turing machine, and alternating Turing machine. N. Blum (1983) introduced a model for which the thesis does not hold. However, the model allows $2^{2^{O(T(n))}}$ parallel threads of computation after $T(n)$ steps. (See Big O notation.) Parberry (1986) suggested a more "reasonable" bound would be $2^{O(T(n))}$ or $2^{T(n)^{O(1)}}$, 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.

For example, it was proven in 1978 that for any ${\textstyle T(n)\geq \log n}$,$$\bigcup _{k=1}^{\infty }T(n)^{k}{\text{-time PRAM}}=\bigcup _{k=1}^{\infty }T(n)^{k}{\text{-space}}$$ In particular, ${\textstyle \bigcup _{k}\log ^{k}n{\text{ PRAM}}=\bigcup _{k}\log ^{k}n{\text{ SPACE}}}$, and polynomial-time PRAM = PSPACE.

$$\bigcup _{c>0}cT(n){\text{-time NONDET PRAM }}=\bigcup _{c>0}2^{cT(n)}{\text{-time }}$$In particular, nondeterministic ${\textstyle O(\log n)}$-time PRAM = NP and nondeterministic polynomial time PRAM = nondeterministic exponential time.

Sequential computation thesis

Related to this is the sequential computation thesis. It states that given any two reasonable definitions A and B, of what it means to have a "sequential computer", for each sequential computer $C_{A}$ according to definition A, there is a sequential computer $C_{B}$ according to definition B, such that the execution time of $C_{A}$ on any problem is upper bounded by a polynomial of the execution time of $C_{B}$ on the same problem.

It is stronger than the Church–Turing thesis, since it claims not only that the computable problems are the same for all computers, but also that the feasibly computable problems are the same for all computers.