If someone solved the P vs. NP problem, would they be able to keep it a secret and make money off of it by, say, starting a software or security company? Or would they only be able to publish it for everyone to know?

Also, would that person (realistically) be at risk of being kidnapped, tortured, killed, etc. by governments?


Edit: not a duplicate because question focuses on the scientist who proves P=NP or P!=NP, whereas another thread focuses on worldwide impact as a result of a proof.

  • 3
    $\begingroup$ Possible duplicate of What would be the real-world implications of a constructive $P=NP$ proof? $\endgroup$ – jmite Feb 13 '18 at 5:02
  • 2
    $\begingroup$ I struggle to view this as a CS question. Community votes, please: offtopic? $\endgroup$ – Raphael Feb 13 '18 at 10:20
  • $\begingroup$ I too am unsure. The part of this question that asks whether it would be possible to make money off the solution seems plausibly on-topic here, but it also feels pretty close to a duplicate of the other question. The part that asks "Would they be at risk of kidnap?" doesn't seem to me like suitable question here; it doesn't seem like a question about computer science, and it seems like a matter of opinion (and calls for speculation). $\endgroup$ – D.W. Feb 13 '18 at 17:18

Most immediately, if they publish it, they would win the Clay Mathematics Institute prize for solving this problem, so there's at least $1 million in it. They would also almost certainly be able to obtain a secure academic position, which would also be worth a significant amount.

Whether there's more money to be made off such a solution depends on a couple of things:

  • Did they prove $\mathrm{P} = \mathrm{NP}$, or $\mathrm{P} \neq \mathrm{NP}$?
  • If they showed $\mathrm{P} = \mathrm{NP}$, do they have a practical algorithm for everything in $\mathrm{NP}$?

For the first, if they proved $\mathrm{P} \neq \mathrm{NP}$, then perhaps nothing really changes. Most people are working under the assumption that this is true (give or take) now anyway. The maths they use may have something special in it that could be commercially useful, it may not.

If they showed $\mathrm{P} = \mathrm{NP}$, this is still not necessarily useful unless you have some way of getting good polynomial time algorithms, having a $\mathcal{O}(n^{2^{1000000}})$ algorithm for SAT is not really more useful than having an exponential one (in fact, would normally be worse, c.f. Alan Perlis).

Now, in the case that's interesting for script writers, if they show $\mathrm{P} = \mathrm{NP}$ and they have a fast algorithm for at least some interesting $\mathrm{NP}$-complete problems, then there are lots of ways to make money. Production planning, microchip layout, data mining, facility location, routing (both computer and otherwise), timetabling, etc. etc. are all major industrial problems, which already attract a lot of money and research, having the best algorithm in any one of these could be very financially lucrative.

Finally, if $\mathrm{P} = \mathrm{NP}$ and there's a fast algorithm for factoring (which is what I'm guessing you mean when you say security), then there is a brief window where someone could make money off that, before everyone just moved to already existing cryptographic schemes that don't rely on the apparent difficulty of factoring. The most white-hat version I can think of is helping ethically sound law enforcement agencies fight crime ("She's a cryptanalyst, he's a streetwise cop, together they fight crime!"). Almost every other use is black-hatted, probably run by organised crime or ethically challenged government agencies, and of dubious financial reward (there's definitely money to be made, but whether the person who discovers the proof makes that money is uncertain). The most extended version of this is that one of the three letter agencies (or equivalent) find out, quietly employ the discoverer, hush-up the discovery, and use the technology to spy on whomsoever they think has something they need to know. This would at least be a steady, probably well paying job, though it's hard to discern the exact salaries of, say, NSA employees, so it's a bit hard to tell.

It's difficult to imagine a sensible case where the person would be kidnapped, tortured or killed1. There's almost always simpler, more reliable and safer ways to get the information than attempting a rather dangerous operation (for example, just pay someone instead), but this is getting well away from the Computer Science part of this question.


  1. As Evil (perfect name :D) points out in the comments, there is actually a potential motive for misdeed by those who are about to lose their jobs to the much better algorithm. My general counter in this case is that murder is insufficient; by the time they find out their businesses are dead in the water, the better solution has been commercialised and they would have to destroy an entire company, all its records, hardware and software. Conversely, they could, probably more easily, steal the technology and get in on the same game (the traditional route in IT - no-one got killed at Xerox PARC :D). My counter to my counter is that if someone found out about the discovery while it was still a one-person/one-computer operation, then you have a thriller movie (PSA time: always encrypt and back-up offsite, and set up a dead-man's switch...).

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.