<p>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 <em>n</em> (input size) and <em>p</em> (number of processors), often under a natural assumption <em>n >> p</em>.</p>

<p>A good starting point is to google for "bulk-synchronous parallelism".</p>

CC BY-SA 4.0
2019-10-21T09:16:29.840Z
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 :/
Gere
CC BY-SA 2.5
2010-12-20T21:42:50.440Z
2010-12-20T21:42:50.440Z
Alexander Tiskin
<p>You might be interested in this paper:</p>

<p><a href="http://www.cs.queensu.ca/home/akl/techreports/superform_updated.ps" rel="nofollow">Superlinear Performance In Real-Time Parallel Computation</a> by Selim Akl.</p>

<p>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".</p>

CC BY-SA 2.5
2010-10-24T04:34:04.583Z
2010-10-24T04:34:04.583Z
Mikhail Glushenkov
<p>If you distribute the task to $p$ (where $p$ is a constant) processors. </p>

<p>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$.</p>

<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$.</p>

<p>But NO complexity change.</p>

CC BY-SA 2.5
2010-09-20T08:03:20.707Z
2010-09-20T08:03:20.707Z
Pratik Deoghare
<p>"you can't compute it with 1 processor, but can compute with 2."</p>

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

<blockquote>
  <p>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)</p>
</blockquote>

<p>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 : </p>

<blockquote>
  <p>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.</p>
</blockquote>

CC BY-SA 2.5
2010-10-24T08:16:34.333Z
Here we have a great example for cost of abstraction. Real computers (as implementations of RM) can be parallelized better  than TMs.
Raphael
CC BY-SA 2.5
2010-10-26T07:38:28.140Z
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
CC BY-SA 2.5
2010-09-20T14:06:10.007Z
2010-09-20T14:06:10.007Z
chazisop
<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-20T15:33:43.567Z
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
CC BY-SA 2.5
2010-09-20T16:21:32.350Z
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
CC BY-SA 2.5
2010-09-21T00:25:31.990Z
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
CC BY-SA 2.5
2010-09-20T10:49:55.883Z
2010-09-20T10:49:55.883Z
jkff
<p>If you mean O(1) processors, then no, computation complexity cannot be reduced.</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-23T18:58:37.160Z
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
CC BY-SA 2.5
2010-08-23T18:59:58.467Z
@Nick: Something other than input size is O(1) :-)
Aryabhata
CC BY-SA 2.5
2010-08-23T19:07:46.533Z
Thanks, I was having trouble thinking of anything else, but I wanted to be sure.
Nick Larsen
CC BY-SA 2.5
2010-09-20T14:27:07.103Z
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
CC BY-SA 2.5
2010-09-20T20:35:13.117Z
@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
CC BY-SA 2.5
2010-08-23T18:49:16.443Z
2010-08-23T18:49:16.443Z
Aryabhata
<p>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?</p>

CC BY-SA 2.5
2010-08-23T18:38:54.030Z
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
CC BY-SA 2.5
2010-08-23T18:40:09.177Z
"Not relative to input size". What do you exactly mean by that? O(1)?
Aryabhata
CC BY-SA 2.5
2010-08-23T18:47:05.013Z
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
<cc.complexity-theory><dc.parallel-comp>
Reducing complexity with parallelism
Nick Larsen
# Reducing complexity with parallelism

(Asked by: username_0 on 2010-08-23)

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?

**Tags:** cc.complexity-theory, dc.parallel-comp
> **Comments:**
> **username_1**: 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?  
> **username_2**: "Not relative to input size". What do you exactly mean by that? O(1)?  
> **username_0**: 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?  

---

## 6 answers

### Answer by username_2 on 2010-08-23. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: @Nick: Something other than input size is O(1) :-)  
> **username_0**: Thanks, I was having trouble thinking of anything else, but I wanted to be sure.  
> **username_10**: 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?  
> **username_2**: @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.  

---

### Answer by username_3 on 2010-12-20. Score: 6

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".

> **Comments:**
> **username_4**: 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 :/  

---

### Answer by username_5 on 2010-10-24. Score: 3

You might be interested in this paper:

[Superlinear Performance In Real-Time Parallel Computation](http://www.cs.queensu.ca/home/akl/techreports/superform_updated.ps) by Selim Akl.

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".


---

### Answer by username_6 on 2010-09-20. Score: 1

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.


---

### Answer by username_7 on 2010-09-20. Score: 1

"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.

> **Comments:**
> **username_8**: Here we have a great example for cost of abstraction. Real computers (as implementations of RM) can be parallelized better  than TMs.  
> **username_7**: 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.  

---

### Answer by username_9 on 2010-09-20. Score: 0

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.

> **Comments:**
> **username_10**: 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.  
> **username_9**: 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.  
> **username_7**: 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).  

---

