Content deleted Content added
→Sequential computation thesis: extended |
|||
Line 5:
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.<ref>{{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}}</ref>
However, the model allows <math>2^{2^{O(T(n))}}</math> parallel threads of computation after <math>T(n)</math> steps. (See [[Big O notation]].) Parberry (1986) suggested a more "reasonable" bound would be <math>2^{O(T(n))}</math> or <math>2^{T(n)^{O(1)}}</math>, in defense of the thesis.<ref name=":0">{{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|doi-access=free}}</ref>
Goldschlager (1982) proposed a model which is sufficiently universal to emulate all "reasonable" parallel models. In this model, the thesis is provably true.<ref>{{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|doi-access=free}}</ref>
Chandra and Stockmeyer originally formalized and proved results related to the thesis for deterministic and alternating Turing machines, which is where the thesis originated.<ref>{{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|doi-access=free}}</ref>
Line 15:
The '''parallel computation thesis''' states that, conditional on any <math display="inline">T(n) \ge \log n</math>, 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 <math display="inline">O\left(2^{n^{O(1)}}\right)</math> processors and word size <math display="inline">O\left(T(n)^2\right)</math>.<ref name=":0" />
== Evidence ==
| |||