Parallel computation thesis: Difference between revisions

Revision as of 09:13, 30 January 2023

Revision as of 22:34, 25 June 2023

Line 1:

{{Short description|Hypothesis in computational complexity theory}}

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 [[Ashok K. Chandra|Chandra]] and [[Larry Stockmeyer|Stockmeyer]] in 1976.<ref name=alternation>{{Cite conference|last1=Chandra|first1=Ashok K.|last2=Stockmeyer|first2=Larry J.|title=Alternation|book-title=FOCS'76: Proceedings of the 17th Annual Symposium on Foundations of Computer Science|pages=98–108|doi=10.1109/SFCS.1976.4|year=1976}}</ref>