Parallel computation thesis: Difference between revisions

Revision as of 01:55, 19 May 2025

Revision as of 01:57, 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>, and with the restriction that the number of processors of the PRAM is no more than exponential in parallel running time, we have<math display="block"> \bigcup_{k=1}^{\infty} T(n)^k \text{-time PRAM} = \bigcup_{k=1}^{\infty} T(n)^k \text{-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'''. Also, for non-deterministic versions,<math display="block">

<math display="block">

\bigcup_{c>0} cT(n) \text {-time NONDET PRAM }=\bigcup_{c>0} 2^{cT(n)} \text {-time }

</math>In particular, nondeterministic <math display="inline">O(\log n)</math>-time PRAM = NP and nondeterministic polynomial time PRAM = nondeterministic exponential time.

== Sequential computation thesis ==

Related to this is the '''sequential computation thesis'''.<ref>{{Cite book |last=Goldschlager |first=Les |title=Computer science: a modern introduction |last2=Lister |first2=Andrew |date=1982 |publisher=Prentice/Hall Internat |isbn=978-0-13-165704-5 |edition=1 |series=Prentice-Hall international series in computer science |___location=Englewood Cliffs, NJ}}</ref>{{Pg|___location=Section 3.2.3}} It states that given any two reasonable definitions A and B, of what it means to have a "sequential computer", for each sequential computer <math>C_A</math> according to definition A, there is a sequential computer <math>C_B</math> according to definition B, such that the execution time of <math>C_A</math> on any problem is upper bounded by a polynomial of the execution time of <math>C_B</math> on the same problem.