Content deleted Content added
Sammi Brie (talk | contribs) Adding short description: "Hypothesis in computational complexity theory" |
m Open access bot: doi added to citation with #oabot. |
||
Line 7:
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>{{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, which adheres to the thesis.<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>
== References ==
| |||