What If... (P?NP Related)

[snow5379]

If you had an algorithm that could solve NP complete problems really quickly would you make more money keeping it as a trade secret for your business or publishing it for the $1,000,000 reward? Even though P!=NP probably it's still an interesting thing to talk about I think.

[naschilling]

Using it for private gain would be much more beneficial. I'm pretty confident that it has already been solved.

[undecim]

Having such an algorithm would give you a technological advantage over anyone who doesn't. If you release it, not only would everyone else have it, but there would be quite a lot of issues with releasing it immediately. It'd be better to let people know you have it (with proof by demonstration), and not release it until the world is ready for it (and in the interim, profit greatly)

[KnightExemplar]

If P = NP, does that not imply that a lot of cryptography can be solved? At very least, RSA (asymmetric cryptography) is an NP problem. And a good number of HTTPS servers are built on top of RSA. Hashing also is an NP problem, so most modern forms of authentication would be invalid by that discovery.

Ignoring the business advantage of P=NP... the criminal/hacker advantage would be insane. It would rely on keeping it a secret however, so people would continuously use HTTPS. In fact, the advantage is so advantageous, that you'd have to keep even the fact the existence of the algorithm a secret.

[markop2003]

That assumes you're in the position to exploit it. Also i don't see why a licensee couldn't betray you and get the award unless you've patented it which would mean releasing it.

[WarDaft]

You could potentially have the worlds best compression algorithm. And you could offer it as a service, as the decompression would not have to reveal the algorithm.

Consider a compression scheme, such that you chose a TM with a write once output tape, whose output is prefixed by a specific sequence in no more than N steps. Given a TM, we can obviously verify it correct in N steps. Furthermore, no more than N states are possibly required. If a TM can emulate one of these TMs in polynomial time, then an NDTM can emulate all machines up to a given size in polynomial time. Thus, you can obtain an almost arbitrarily effective compression mechanism for a given bit string by varying N. Furthermore, you can distribute the result to others who then have no means by which to reverse engineer your algorithm from the solution you provided. So you could, for example, provide the worlds most effective video compression service.

You could likely use a similar method for all kinds of optimization problems and the like. You could just generate efficient programs at will for just about any field.

[EvanED]

Using it for private gain would be much more beneficial. I'm pretty confident that it has already been solved.

"Bruce Schneier already has a backup plan for when the 2nd person discovers that P = NP."

[Carnildo]

If you had an algorithm that could solve NP complete problems really quickly would you make more money keeping it as a trade secret for your business or publishing it for the $1,000,000 reward? Even though P!=NP probably it's still an interesting thing to talk about I think.

I'd release it. As was noted about the fission bomb, scientific knowledge cannot be hidden forever, and by releasing, I ensure that I get credit.

[WarDaft]

I'd release it. As was noted about the fission bomb, scientific knowledge cannot be hidden forever, and by releasing, I ensure that I get credit.

Hmm.... credit... world domination... credit... world domination.

I think I'd definitely go with the credit world domination.

Whew.... that was a close one.

[sjorford]

I'd release it. As was noted about the fission bomb, scientific knowledge cannot be hidden forever, and by releasing, I ensure that I get credit.

I wouldn't worry about that, you're guaranteed not to get credit anyway.

[radams]

Your reward for publishing would be more than just the $1m Clay prize. You'd certainly win a Fields medal and a Turing award too (another $265,000), and could comfortably claim a post as distinguished professor in the university of your choice (six-figure income for life). Compared to that, constantly finding clients who want you to crack RSA for them seems too much like work.

[lalop]

What if you released and patented it?

[WarDaft]

Your reward for publishing would be more than just the $1m Clay prize. You'd certainly win a Fields medal and a Turing award too (another $265,000), and could comfortably claim a post as distinguished professor in the university of your choice (six-figure income for life). Compared to that, constantly finding clients who want you to crack RSA for them seems too much like work.

It's a lot more broad reaching than that.

See my comment about how you could, for example, revolutionize lossy and lossless compression, and how you could provide it as a service that others cannot replicate by inspection. Likewise, you could apply it to fields of medicine, breaking and building encryption schemes (we're talking military level contracts), and a myriad of other possible areas each of which would substantially exceed a mere million dollars. You would also be far more likely to be recognized and given credit for your discovery, as you would become notable before the work. Once you've seized control of the potential markets, then you can release it and claim the prize.

Unless of course you've only found a non-constructive proof which offers no useful algorithms, merely promising that we can have no real feeling of digital safety. That you can publish.