“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

steps for inputs of length n is decidable by a non-branching machine 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) introduced a model for which the thesis does not hold.^[2]

However, the model allows

parallel threads of computation after

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

, in defense of the thesis.^[3]

Goldschlager (1982) proposed a model which is sufficiently universal to emulate all "reasonable" parallel models, which adheres to the thesis.^[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]

References

1. ^{{Cite conference|last1=Chandra|first1=Ashok K.|last2=Stockmeyer|first2=Larry J.|title=Alternation|booktitle=FOCS'76: Proceedings of the 17th Annual Symposium on Foundations of Computer Science|pages=98–108|doi=10.1109/SFCS.1976.4|year=1976}}
2. ^{{Cite journal|journal=Information Processing Letters|last=Blum|first=Norbert|title=A note on the 'parallel computation thesis'|volume=17|issue=4|pages=203–205|year=1983|doi=10.1016/0020-0190(83)90041-8}}
3. ^{{Cite journal|doi=10.1145/8312.8317|last=Parberry|first=I.|title=Parallel speedup of sequential machines: a defense of parallel computation thesis|journal=ACM SIGACT News|volume=18|issue=1|pages=54–67|year=1986}}
4. ^{{Cite journal|doi=10.1145/322344.322353|last=Goldschlager|first=Leslie M.|title=A universal interconnection pattern for parallel computers|journal=Journal of the ACM|volume=29|issue=3|pages=1073–1086|year=1982}}
5. ^{{Cite journal|doi=10.1145/322234.322243|last1=Chandra|first1=Ashok K.|last2=Kozen|first2=Dexter C.|last3=Stockmeyer|first3=Larry J.|title=Alternation|journal=Journal of the ACM|volume=28|issue=1|pages=114–133|year=1981}}