# Does there exist a problem for which no existing solution can be parallelized on a Turing machine?

I'm asking for problems for which we know there exists a solution for which an equivalent parallel program cannot be written on a Turing machine.

Alternatively, have we proven the opposite to be true - that for every problem, there exists at least one parallelizable solution?

• What is "the" definition of parallelisable, of parallelisable algorithm? Commented Jun 25, 2020 at 22:25
• @greybeard: To answer your question strictly: "Able to be made parallel." Basically, what I'm wondering is: Given an infinite amount of resources, can we parallelize all solutions to EVERY solvable problem, or are there solutions that absolutely CANNOT be parallelized? Commented Jun 25, 2020 at 22:29
• I think you're going to need to give us a clearer definition. Any algorithm can be run on a parallel processor, e.g., by leaving all but one processor idle.
– D.W.
Commented Jun 25, 2020 at 23:04
• @D.W. OK. Here, a parallelizeable algorithm is one where at least one task within that algorithm can be split into asynchronous tasks. For example, a computer can calculate the sum of 1 and 1 by calculating 1 XOR 1, and 1 AND 1, and mushing those bits together. The first two tasks could be done asynchronously, so the algorithm is parallelizeable. Commented Jun 25, 2020 at 23:30
• Again, I can always take any algorithm, and split it into two asynchronous tasks: the first task executes the algorithm, and the second executes a no-op. I think you need a more careful definition of parallelizable.
– D.W.
Commented Jun 26, 2020 at 6:20

The question is not precisely defined, so it's not really amenable to a precise technical answer at this stage. But a common view/hypothesis/expectation is that there exist problems that are inherently sequential, in the sense that they cannot be substantially sped up on a parallel computer, no matter how many parallel processors you have. A weak version of this view is implied by the conjecture that $$NC \ne P$$ (see https://en.wikipedia.org/wiki/NC_%28complexity%29), which is conjectured but not known to hold. In particular, P-complete problems are good candidates for problems that don't benefit much from parallelization. There are stronger versions of this view; for instance, in cryptography, timelock puzzles utilize functions that are believed to be inherently sequential: a parallel processor cannot speed them up very much.