# Any algorithm polynomial time with infinite space?

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?

• 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. – Omar Aug 10 '17 at 8:00
• 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. – rus9384 Aug 10 '17 at 8:41
• @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... – MrFrety Aug 10 '17 at 8:52
• Consider comparison-based sorting. It cannot be done, in parallel, in less than O(log n) steps, for n elements. – Omar Aug 10 '17 at 9:30
• @Omar, it can be done in polynomial time so, it's not a counterexample. – rus9384 Aug 10 '17 at 10:41

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.
• @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). – Ariel Aug 10 '17 at 16:00