Parallel computation thesis: Difference between revisions

Revision as of 02:19, 19 May 2025

Revision as of 02:25, 19 May 2025

Line 23:

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

== Other theses ==

== Sequential computation thesis ==

=== Extended parallel computation thesis ===

The '''extended parallel computation thesis'''<ref>{{Cite journal |last=Dymond |first=Patrick W. |last2=Cook |first2=Stephen A. |date=1980-10 |title=Hardware complexity and parallel computation |url=https://ieeexplore.ieee.org/document/4567837/ |journal=21st Annual Symposium on Foundations of Computer Science (sfcs 1980) |pages=360–372 |doi=10.1109/SFCS.1980.22}}</ref> states that both of these are true:

* Turing machine (head reversal, tape space) and PRAM (parallel time, processor count) are simultaneously polynomially related.

* PRAM parallel time and PRAM processor count are polynomially related.

=== 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", their execution times are polynomially related. Concretely, it means that 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.