Parallel computation thesis: Difference between revisions

Revision as of 01:55, 19 May 2025

Revision as of 01:55, 19 May 2025

Line 9:

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>

For example, it was proven in 1978<ref>{{Cite journal |last=Fortune |first=Steven |last2=Wyllie |first2=James |date=1978 |title=Parallelism in random access machines |url=https://doi.org/10.1145/800133.804339 |journal=Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 |___location=New York, New York, USA |publisher=ACM Press |pages=114–118 |doi=10.1145/800133.804339}}</ref> that for any <math display="inline">T(n) \ge \log n</math>,<math display="block"> \bigcup_{k=1}^{\infty} T(n)^k \text{-time PRAM} = \bigcup_{k=1}^{\infty} T(n)^k \text{ SPACE-space} </math> In particular, <math display="inline">\bigcup_k \log^k n \text{ PRAM} = \bigcup_k \log^k n \text{ SPACE}</math>, and polynomial-time PRAM = PSPACE.

<math display="block">