If I had an arbitrary amount of space at my disposal, couldn't I vectorize/parallelize any program in such a way that it would only need one step? For example, I could let my CPU have an inbuilt look-up-table for the function (x+y)/z with 3 input values instead of doing the calculation in 2 steps.
Does there exist any proof that something like that isn't possible?
$\begingroup$
$\endgroup$
9
-
$\begingroup$ It is not, in general, possible. Many theoretical models (e.g., Turing machines) already have infinite tape/storage, including the (parallel) PRAM model I'd guess. Not everything is fully (or even at all) parallelizable. Some dependencies may exist, enforcing sequential processing. In other words, many problems have non-trivial lower bounds on their parallel running times. $\endgroup$– OmarCommented Aug 10, 2017 at 8:00
-
$\begingroup$ In fact, it depends on the program: there presumably exist programs that do not allow more than constant speed up. E.g. you need to know the result for previous step before calculating next step. $\endgroup$– rus9384Commented Aug 10, 2017 at 8:41
-
$\begingroup$ @rus9384 "you need to know the result for previous step before calculating next step" - Has this been proven? I tried to make plausible with my example that it might always be possible to circumvent this by making a pre-defined combined function... $\endgroup$– MrFretyCommented Aug 10, 2017 at 8:52
-
$\begingroup$ Consider comparison-based sorting. It cannot be done, in parallel, in less than O(log n) steps, for n elements. $\endgroup$– OmarCommented Aug 10, 2017 at 9:30
-
$\begingroup$ @Omar, it can be done in polynomial time so, it's not a counterexample. $\endgroup$– rus9384Commented Aug 10, 2017 at 10:41
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
3
If you don't allow preprocessing, then the answer is no (at least when talking about standard models of computation such as the Turing machine or a random access machine). The reason follows from the fact that (in reasonable models) writing to memory requires time, hence the amount of memory used is upper bounded by the running time.
The notion of preprocessing is captured in complexity by machines who have access to an advice, alongside with the input. For example, the class $\mathsf{P/Poly}$ consists of all problems solvable using polynomial machines, who given a length $n$ input, have access to an advice string of length $poly(n)$. Note that the advice is the same for all inputs of the same length, you can think of this advice as your preprocessing. If, as in your example, you allow too much preprocessing, then everything is solvable in a single step, which makes this situation uninteresting (and indeed, it is not realistic to imagine you have the answer ready for any possible input). In the language of Turing machines who take advice, you can say that $\mathsf{P/EXP}$ with random access to the advice is the class of all languages (your advice can include the answers for all inputs). This means that allowing the advice to be too long makes the game too easy.
-
$\begingroup$ I think it's a little more complex than this: the question talks about parallelism so an unreasonable number of threads could potentially write an unreasonable amount of data in constant time. $\endgroup$ Commented Aug 10, 2017 at 15:40
-
$\begingroup$ @DavidRicherby, only if they'll programmed to do it, yes? However, there is no way to use excess threads. $\endgroup$– rus9384Commented Aug 10, 2017 at 15:44
-
2$\begingroup$ @DavidRicherby The space used is now bounded by the maximal running time $\times$ the number of threads, so I don't think parallelism has much effect on the question (at least in its current formulation). $\endgroup$– ArielCommented Aug 10, 2017 at 16:00