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$ 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$
    – Omar
    Aug 10 '17 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$
    – rus9384
    Aug 10 '17 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$
    – MrFrety
    Aug 10 '17 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$
    – Omar
    Aug 10 '17 at 9:30
  • $\begingroup$ @Omar, it can be done in polynomial time so, it's not a counterexample. $\endgroup$
    – rus9384
    Aug 10 '17 at 10:41

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$ Aug 10 '17 at 15:40
  • $\begingroup$ @DavidRicherby, only if they'll programmed to do it, yes? However, there is no way to use excess threads. $\endgroup$
    – rus9384
    Aug 10 '17 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$
    – Ariel
    Aug 10 '17 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.