Parallel computation thesis: Difference between revisions

Revision as of 02:17, 19 May 2025

Revision as of 02:19, 19 May 2025

Line 12:

Given two models of computation, such as Turing machines and PRAM, they would have computational resource usages. For Turing machines, the resources can be tape space, sequential time, number of times the read/write head changes direction, etc. For PRAM, the resources can be parallel time, total number of processors, etc.

GivenConditional on a function <math>T(n)</math>, saying that the use of one resource R in one model is '''polynomially related''' to the use of another resource R' in another model means the following. Given a problem that can be solved with some computation according to the first model, consuming only <math>T(n)^k</math> amount of resource R for some <math>k > 0</math>, there exists another computation according to the second model, consuming only <math>T(n)^{k'}</math> of resource R' for some <math>k' > 0</math>. And ''vice versa''.

The '''parallel computation thesis''' states that, conditional on any <math display="inline">T(n) \ge \log n</math>, the use of tape space in Turing machines is polynomially related to the use of parallel time in PRAM for which the total number of processors is at most exponential in parallel time.

== Evidence ==