# Reducing complexity with parallelism

Is it possible (slash can you provide an example) to reduce computational complexity of a problem by using a parallel algorithm which does not require a number of processors relative to the input size?

• Could you clarify your question a bit? Trivially constant number of processors -> at best you can improve the running time by a constant factor. I guess this wasn't what you mean? – Jukka Suomela Aug 23 '10 at 18:38
• "Not relative to input size". What do you exactly mean by that? O(1)? – Aryabhata Aug 23 '10 at 18:40
• I mean O(1) processors. @Jukka: that is what I mean, can computational complexity only be reduced by adding a number of processors relative to the input size? – Nick Larsen Aug 23 '10 at 18:47

If you mean O(1) processors, then no, computation complexity cannot be reduced.

Simply line up the work done by each processor and do it on a single one. If you are worried about synchronization, then one processor can easily emulate that.

• Thank you for the quick answer. Without creating another question for something so closely related, is it possible to reduce computational complexity using a number of processors relative to something other than input size? – Nick Larsen Aug 23 '10 at 18:58
• @Nick: Something other than input size is O(1) :-) – Aryabhata Aug 23 '10 at 18:59
• Thanks, I was having trouble thinking of anything else, but I wanted to be sure. – Nick Larsen Aug 23 '10 at 19:07
• W.R.T. whether you can achieve a speedup with a number of processors which grows with some quantity other than input size, I'm not sure that the answer is 'no'. There are problems whose complexity grows with some parameter that is different (although obviously not independent of) input size. What if for some graph problem, I allowed you a number of processors related to the tree-width of the graph, for example? – Aaron Roth Sep 20 '10 at 14:27
• @Aaron: If number of processors allowed is related to the input somehow, then yes, we cannot say "no" for sure. Of course, unless we are specific, it is a meaningless question. – Aryabhata Sep 20 '10 at 20:35

There is an emerging field of coarse-grained parallel algorithms, where the running time (and other computational resource consumption) is regarded as a function of independent parameters n (input size) and p (number of processors), often under a natural assumption n >> p.

A good starting point is to google for "bulk-synchronous parallelism".

• Can the complexity class change if you allow the hardware to scale with the input data? I'm having trouble to google that as a layman :/ – Gerenuk Oct 21 '19 at 9:16

You might be interested in this paper:

He provides examples of computational problems in which "the sequential solution is more than $n$ times slower than an $n$-processor parallel solution"; this is done by creatively interpreting the concept of a "computational problem".

If you distribute the task to $p$ (where $p$ is a constant) processors.

Then complexity may be $O(f(n)/p) \rightarrow O((1/p)f(n)) \rightarrow O(cf(n)) \rightarrow O(f(n))$ where $c=1/p$.

What we use parallelism is to reduce run-time of the task i.e. if a task is taking $T$ seconds then with parallelism it may take $T/p + SomeMoreTime$.

But NO complexity change.

"you can't compute it with 1 processor, but can compute with 2."

This is not possible, assuming that both processors are TMs or a less powerful model. From wikipedia , for multi-tape machines :

This model intuitively seems much more powerful than the single-tape model, but any multi-tape machine, no matter how large the k, can be simulated by a single-tape machine using only quadratically more computation time (Papadimitriou 1994, Thrm 2.1)

Also for multi-head machines, from "Linear time simulation of multihead turing machines with head — To-head jumps" by Walter J. Savitch and Paul M. B. Vitányi :

The main result of this paper shows that, given a Turing machine with several read-write heads per tape and which has the additional one move shift operation "shift a given head to the position of some other given head", one can effectively construct a multitape Turing machine with a single read-write head per tape which simulates it in linear time; i.e. if the original machine operates in time T(n), then the simulating machine will operate in time cT(n), for some constant c.

• Here we have a great example for cost of abstraction. Real computers (as implementations of RM) can be parallelized better than TMs. – Raphael Oct 24 '10 at 8:16
• What RM stands for? If that was a misstype and you mean TM, I disagree. Multitape/multihead TMs do not have to worry about processor communication and Amdahl's law. Furthermore, I don't see how a computer can perform better than a random access TM and vice versa, i.e. I believe they are equivalent. – chazisop Oct 26 '10 at 7:38

Perhaps "parallel or" (given two functions returning a boolean, tell whether one of them returns true, given that any of them, but not both, might fail to terminate) might be what you're talking about: you can't compute it with 1 processor, but can compute with 2.

However, this much depends on which computational model you'll be using, whether you're given the processes as black boxes or as their description which you can interpret yourself, etc.

• This seems false, unless you are working in some severely limited model. A single processor could just interleave the instructions that would otherwise run on 2, causing at most a 2x + O(1) slowdown. I guess by black box'' you mean that interleaving is impossible? Even then, if you may terminate black box computations that take too long, you can still simulate two processors by repeatedly guessing-and-doubling the required computation length for each process. – Aaron Roth Sep 20 '10 at 15:33
• But that, in turn, requires us to be able to terminate computations. I mean that you can't do parallel or on 1 processor in a model where the only thing you can do is to run a computation until it finishes. – jkff Sep 20 '10 at 16:21
• Now I understand what you meant, but I believe it is not complete. You cannot compute it with 2 neither. If one machine keeps running and the other answers YES, the answer is YES. But what if it returns NO? You cannot answer in a deterministic fashion, because you do not know if the machine that is still running or is it stuck (i.e. the HALTING problem). – chazisop Sep 21 '10 at 0:25