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.^[1]

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.^[2] 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.^[3] Goldschlager (1982) proposed a model which is sufficiently universal to emulate all "reasonable" parallel models. In this model, the thesis is provably true.^[4] Chandra and Stockmeyer originally formalized and proved results related to the thesis for deterministic and alternating Turing machines, which is where the thesis originated.^[5]

Definition

Given two models of computation, such as Turing machines and PRAM, they would have computational resource usages. For Turing machines, the resources can be tape space, sequential time, number of times the read/write head changes direction, etc. For PRAM, the resources can be parallel time, total number of processors, etc.

Conditional on a function $T(n)$ , saying that the use of one resource R in one model is polynomially related to the use of another resource R' in another model means the following. Given a problem that can be solved with some computation according to the first model, consuming only $T(n)^{k}$ amount of resource R for some $k>0$ , there exists another computation according to the second model, consuming only $T(n)^{k'}$ of resource R' for some $k'>0$ . And vice versa.

The parallel computation thesis states that, conditional on any ${\textstyle T(n)\geq \log n}$ , the use of tape space in Turing machines is polynomially related to the use of parallel time in PRAM for which the total number of processors is at most exponential in parallel time.

The restriction on "at most exponential" is important, since with a bit more than exponentially many processors, there is a collapse: Any language in NP can be recognized in constant time by a shared-memory machine with ${\textstyle O\left(2^{n^{O(1)}}\right)}$ processors and word size ${\textstyle O\left(T(n)^{2}\right)}$ .^[3]

If the parallel computation thesis is true, then one implication is that "fast" parallel computers (i.e. those that run in polylogarithmic time) recognize exactly the languages in polyL.^[6]

Evidence

It was proven in 1978^[7] that for any ${\textstyle T(n)\geq \log n}$ , and with the restriction that the number of processors of the PRAM is no more than exponential in parallel running time, we have $\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. Note that the exponential amount of processors is likely required. Specifically, suppose that only a polynomial number of processors are required for some PSPACE-complete problem, then it would show that PSPACE = P, a major unresolved hypothesis that is expected to be false.

Also, for non-deterministic versions, $\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.

Other theses

Extended parallel computation thesis

The extended parallel computation thesis^[8] states that both of these are true:

Turing machine (head reversal, tape space) and PRAM (parallel time, processor count) are simultaneously polynomially related.
PRAM parallel time and PRAM processor count are polynomially related.

One implication would be that "small and fast" parallel computers (i.e. those that run in both polylogarithmic time and with polynomially many processors) recognize exactly the languages in NC.^[6]

Sequential computation thesis

Related to this is the sequential computation thesis.^[9]^{: Section 3.2.3} It states that given any two reasonable definitions A and B, of what it means to have a "sequential computer", their execution times are polynomially related. Concretely, it means that 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.

References

^ Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Alternation". FOCS'76: Proceedings of the 17th Annual Symposium on Foundations of Computer Science. pp. 98–108. doi:10.1109/SFCS.1976.4.
^ Blum, Norbert (1983). "A note on the 'parallel computation thesis'". Information Processing Letters. 17 (4): 203–205. doi:10.1016/0020-0190(83)90041-8.
^ ^a ^b Parberry, I. (1986). "Parallel speedup of sequential machines: a defense of parallel computation thesis". ACM SIGACT News. 18 (1): 54–67. doi:10.1145/8312.8317.
^ Goldschlager, Leslie M. (1982). "A universal interconnection pattern for parallel computers". Journal of the ACM. 29 (3): 1073–1086. doi:10.1145/322344.322353.
^ Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternation". Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243.
^ ^a ^b Parberry, Ian; Schnitger, Georg (1988-06-01). "Parallel computation with threshold functions". Journal of Computer and System Sciences. 36 (3): 278–302. doi:10.1016/0022-0000(88)90030-X. ISSN 0022-0000.
^ Fortune, Steven; Wyllie, James (1978). "Parallelism in random access machines". Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78. New York, New York, USA: ACM Press: 114–118. doi:10.1145/800133.804339.
^ Dymond, Patrick W.; Cook, Stephen A. (October 1980). "Hardware complexity and parallel computation". 21st Annual Symposium on Foundations of Computer Science (sfcs 1980): 360–372. doi:10.1109/SFCS.1980.22.
^ Goldschlager, Les; Lister, Andrew (1982). Computer science: a modern introduction. Prentice-Hall international series in computer science (1 ed.). Englewood Cliffs, NJ: Prentice/Hall Internat. ISBN 978-0-13-165704-5.