0
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ What is "the" definition of parallelisable, of parallelisable algorithm? $\endgroup$
    – greybeard
    Commented Jun 25, 2020 at 22:25
  • $\begingroup$ @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? $\endgroup$
    – moonman239
    Commented Jun 25, 2020 at 22:29
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Jun 25, 2020 at 23:04
  • $\begingroup$ @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. $\endgroup$
    – moonman239
    Commented Jun 25, 2020 at 23:30
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Jun 26, 2020 at 6:20

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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