7

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?

  • 1
    Here's how it was made - the Infinity Improbability generator just popped into existence when the Finite Improbability generator was fed the exact likelihood of the other one existing (that is, as a random guess, something like 0.000000002%.. or smaller. 'Twas a number, not an algorithm, as I understand it.). – Izkata Sep 27 '12 at 3:35
  • @izkata That is a parametre though, fed into an algorithm though ;) but yes I was trying to find that somewhere! – AncientSwordRage Sep 27 '12 at 6:23
7

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.

  • THIS! Exactly what I meant. Was this intended? – AncientSwordRage Sep 26 '12 at 20:38
  • @Pureferret, I doubt it. But I don't have much to back that up besides gut feeling. – Winston Ewert Sep 26 '12 at 22:24
  • 1
    What exactly do you mean by given access to non-determinism? Coming from a CS background, that sounds like gibberish to me... – Izkata Sep 27 '12 at 0:48
  • @Izkata, see en.wikipedia.org/wiki/Non-deterministic_Turing_machine, its something you might not have covered in CS if you didn't do it at the graduate level. – Winston Ewert Sep 27 '12 at 3:11
  • @WinstonEwert I suggest editing that into the answer somewhere, because "non-determinism" is far too generic. What you're talking about is unrelated to non-deterministic algorithms, which are what I was thinking of. – Izkata Sep 27 '12 at 3:21
7

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.

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.

  • Agreed. If you're just infinitely lucky, then there's nothing that would prevent you from randomly testing the correct answer first. – John O Sep 26 '12 at 18:00
2

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.

  • 1
    But if you could reduce the problem of discovering a Infinite Improbability drive (P) to something that was NP (i.e. the Finite Improbability drive) you could develop the former. No? – AncientSwordRage Sep 26 '12 at 12:44
  • 1
    You're thinking along the right lines, in that all NP problems are reducible to other NP problems, yes. However, there is a better definition that ignorant me is incapable of explaining... they're pretty specific about what is an NP problem. And I'm pretty sure "finding magic" isn't one of them. I think they have proven that the old arcade video games are mostly NP in nature, so you'd be able to play the perfect game of Pacman or Donkey Kong though. That has to be some sort of consolation. – John O Sep 26 '12 at 12:56
  • 1
    An Infinite Improbability drive is messing with quantum probability. As I understand it, the way it's supposed to work is that there's a miniscule, statistically impossible chance for the ship to suddenly be in another place. Now normally this would never happen, but the IP drive can access the quantum waveform and collapse it into a different configuration. It should be possible to do literally anything with it, not just move a ship around. – SaintWacko Sep 26 '12 at 13:32
  • 1
    Actually, most of what you say about NP problems is only true for NP-complete problems. – Winston Ewert Sep 26 '12 at 19:39
  • 1
    Your description of P and NP problems is not really accurate. P problems are solved in polynomial time, N-P are (non-deterministic polynomial) able to be verified in polynomial time, but may not (or may) be able to be solved in polynomial time. There certainly ways of solving NP problems that are not "random", just not polynomial. – NominSim Sep 26 '12 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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