Hacker News Reader

Comment by tsimionescu | Hacker News Reader

Not necessarily. There are problems you can't speed up even if you are given a literal infinity of processors - the problems in EXP for example (well, EXP - NP). Even for NP problems, the number of processors you need for a meaningful speed up grows proportionally to the size of the problem (assuming P!=NP).

View on HN

Computational complexity and parallelism are orthogonal. Many EXP algorithms are embarrassingly parallel. You still have to do 2^n calculations, but if you have 1000 processors then it will take 1000 times less wall clock time because you're doing 1000 calculations at once.

The reason parallelism doesn't "solve" EXP problems is that parallelism grows linearly against something whose time complexity grows exponentially. It's not that it doesn't work at all, it's that if you want to solve the problem for 2n in the same time as for n, you need to double the number of processors. So the number of processors you need to solve the problem in whatever you define as a reasonable amount of time grows exponentially with n, but having e.g. 2^n processors when n is 1000 is Not Gonna Happen.

Having 1000 processors will still solve the problem twice as fast as 500, but that's not much help in practice when it's the difference between 50 billion billion years and 100.

But what if the processor may be made organic, or encoded in DNA, so that replication and protein synthesis is akin to solving the problem? The "computer" grows exponentially, rather than linearly, and so for larger problems, it grows to the size that solves the problem?

Or we end up with grey goo...

Are there any examples of reusable "computers" like this? I've seen some demonstrations but they are not generic to the problem and reusable, they seem to have the data encoded in the makeup of the "computer" itself.

I write computers in quotation marks because even if they solve computational problems they are so different from what we are calling computers today, eg: mold growing in a maze and similar.

None that are usable i'm sure - it's merely a theoretical idea.

A problem that is not in NP is, by definition, a problem that can't be solved in polynomial time even with an infinity of processors (or equivalently, with speculative execution given a perfect oracle). So, it can't be embarrassingly parallel.

So, a problem in EXP - NP (that is, it can be solved in exponential time, but it can't be solved in polynomial time even if given an infinity of processors) will require exponentially more time to solve for a higher n than a lower n, regardless of how many processors you have - even up to infinity. You may get some kind of speed-up with more processors, but it will not be enough to remove the exponential runtime blow-up.

An example of a problem like this is the Travelling Salesman Problem. As far as is known right now, there isn't even a non-determinstic algorithm that can solve the problem in polynomial time. Even if you had an infinity of processors, and could solve the problem for 1000 cities in 1 minute, you would still need ~2^1000 minutes to solve the problem for 2000 cities. Note: this bound is not proven, there may be some non-deterministic algorithm that can solve it in polynomial time.

I will also note that even for a problem that is in EXP and in NP, so an EXP problem that is embarrassingly parallel, doubling the problem size would require 2^n more processors to keep the same run time, not 2n (assuming it's time complexity is O(2^n)).

Reply on news.ycombinator.com