Does Douglas Adams use of 'Infinite Improbability' allude to P=NP?

Question

Having just re-awakened the old P=NP post, I started to think: Is Douglas Adams's description of the discovery of the Infinite Improbability drive via use of the Finite Improbability device a description of where P=NP is used to solve a problem? Is this his explanation of the problem?

My point, re-explained: It's my understanding is that the 'scientists' discovered the finite improbability drive, by some algorithm or understanding that let them put in the right parametres, crank a mathematical handle and get out the finite improbablity drive, they knew the guess work in. They then attempted to find the infinite improbability drive in the same way, apply an algorithm and crank the handle.

But this was taking too long (it wasn't polynomial time, perhaps it was N^p, with p being the probability) so the scientists gave up. However the discoverer of the IID used the Finite Improbability drive to guess the solution to whatever algorithm or equation, and the parametres involved, i.e he solved it as a P problem as an NP problem.

I can't find anything on the web discussing this, but I may have missed something.

Is this (or something similar) what Douglas Adams meant with this description? If not what did he mean?

Answer 1

Sort of.

One way of defining NP is that the question can be decided in polynomial time given access to non-determinism. As it turns out, non-determinism can be thought as equivalent to having a computer which succeeds if it has a non-zero probability of success. Essentially, non-determinism is equivalent to the finite probability device.

So given a device like a finite improbability device, any improbable event can be rendered probable. We can use that to build a computer which has access to non-determinism. The distinction between P and NP is then moot, because P and NP run at the same speed on a nondeterministic computer. Theoretically, P and NP are still distinct, but the distinction is no longer useful.

Answer 2

It is worthwhile to note that the N in NP cannot only be applied to polynomial problems: If X is a particular set of problems that can be decided in a time bounded by a given characterisation (that is, polynomial for P or exponential for EXP) by a deterministic Turing Machine (DTM), then NX will be the set of problems that can be decided by a non-deterministic Turing Machine (NTM).

So the question is how the FID truly works. Do you have to solve a problem that can be decided by a DTM in polynomial time every time you want to jump? If you built a machine that used the FID to remove the required non-determinism from the run of a TM, you would essentially have built an NTM. This actually makes sense, because although the problem space is (or rather might be) infinite, one particular instance of the problem is always finite. So the probability to always "guess" correctly is finite. In this sense, the FID would be the technological equivalent to the computation model of an NTM. So, in general, in a universe with an FID, there is no practical difference between any X and its corresponding NX class of problems, but it would still be unknown whether they are actually equal (as they are defined over TMs, not IDs).

However, it doesn't make sense to argue about the total runtime of an algorithm that crunches an infinite input, as in all but some trivial cases that would be infinite as well.

If IID is just some sort of mathematical problem, that once solved just hands you some insight to build a machine that implements some kind of propulsion, then the question is how hard is this problem? We have no indication whatsoever that it would fall in the class of NP-complete problems. There are a ton of PSPACE (=NPSPACE) problems, and actually even some NEXPTIME. If it was PSPACE your magical advancedly technological FID would be no use to you, you'd wait just as long.

So, the relationship between any X and NX would be like "fixed improbability drive" and "finite improbability drive". It'd seem the infinite improbability drive would rather correspond to a machine that decides every single problem in constant time, regardless of its complexity on a DTM or NTM because an infinitely improbable event is basically one that never happens. There are no such events thinkable: Even two nuclear warheads spontaneously transforming into a bowl of petunias and a very surprised looking sperm whale is not an impossible event. It is just so unlikely nobody bothers to put a warning sticker on such warheads.

To finally answer your question then; No, I don't think Adams would have done such a pop-science blunder. His wibbly-wobbly parts (in lack of a better term) are always intentional and work more in an ironic manner. The IID slightly reminds us of the non-determinism issue as it does something mind-bogglingly hard in a spectacularly efficient way, just as an NTM would. But this similarity is quite superficial, as I tried to point out in the previous paragraphs.

Answer 3

I believe that you could use an infinite improbability drive as part of an NP solver that would make P=NP.

Say you tune your IID so that when you randomly select a candidate solution, it gives you the actual solution. By definition, for NP problems, verifying the correctness of the solution is relatively easy.

Done.

The hard part is getting the infinite improbability drive.

Answer 4

I do not see how that could be the case. Very briefly, P and NP are two classes of computational problems. The P problems can be solved in some reasonable period of time with well-known algorithms. The NP problems are believed (but not yet proven) to be such that the only way to solve them is to try every possible solution essentially randomly until you get the right answer. However, all NP problems are similar in a way that if you discovered an algorithm that allowed you to solve an NP more quickly, that algorithm would apply to all other NP problems. If you've ever tinkered with the math that shows how many possible solutions exist in the solution-space, you might see why this was a big deal. Numbers in some cases that are so large they have no names, only notations.

There are real world implications if P does happen to equal NP (and few that we aren't already living if it does not). For instance, one such problem is "Given a delivery route to these 100 locations, which is the most efficient route to take". If you could solve that in some reasonable amount of time, your delivery company would (probably) use 5% less fuel per year. In turn, a 5% reduction from some large carrier fleets, and we'd probably see $1.50/gallon gasoline again in the United States. And there are many such problems. Computer graphics, meteorology simulations, lots of them. P=NP has many real-world science-fictiony implications (mostly dealing with efficiencies).

But instantaneous travel to distant locations is not one of them.