Ask HN: P=NP, what do you do?

let people make a shopping list, then give them the best deal there is on all the things combined, with as few shipments and registrations as possible, maybe let them pick how many max new stores, and let them keep a list of stores they like -- and once you've made a bunch off that, announce how you did it, claim the million dollar prize and tada - the first mathematician i'm aware of who didn't care about the world's ridiculousness, yet wanted to cash in.<p>if you really want to give a finger to the academia though, just publish it - and include a long essay on all the various ways the academic institutions hindered your progress, how bureaucratic they are, and how little they actually care about advancing knowledge. further, publish it on a blog instead of an academic journal, ask for peer review, and don't mention your university once anywhere on the blog. that'll show 'em, those punks.

Bid the spy agencies against each other. Make sure you tell the Americans that you are really working for them so they don't kill you and they also protect you from all the other people that want to kill you.<p>Edit: Who I am kidding, the Americans would not want the other countries to know P=NP and talking to anyone else would be grounds for disappearance. So there would be no bidding war, you'd have to take what you can get from the NSA/CIA. Anything less than 1M a year for life would be insulting and they know that.

Answer from Cook: www.cs.toronto.edu/~sacook/homepage/JACMpvsnp.ps<p>Highlights - Computers could find formal proofs for any theorem with a reasonable length - All you need then is a good recognition algorithm for formal proofs - Then you can just work on recognizers for good novels / music / etc and have it churn out classics<p>The other example (I forget the source) is that if you have a P time formula for safety checking the designs of nuclear power plant, if P = NP you can efficiently generate a list of the designs of all possible safe nuclear power plants.<p>So you can go from P-time checkable constraints to P-time enumeration of things which fill the constraints.

I've always thought that this would make a great plot for a science fiction novel. A <i>computer science</i> fiction novel. There would be lots of intrigue, as the guy was tracked down by the NSA and covertly outwitted his opponents using his proof, until a final showdown where he discovers the horrifying truth about who else knows that P=NP, and what happens to everyone else who's ever proven it.<p>So...should I look for a literary agent or try and bootstrap this myself by hiring a private press? ;)

Make my salesmen travel more efficiently?

Test driven development would take on a new meaning, with the programmer a writing collection of tests and letting the computer find the shortest program that makes them pass.

I would post a question on HN saying "P=NP, what do you do?" and then take the best suggestion.

You can break a lot of crypto - so if illegality is your speciality, you can break whatever you want. If you want to remain legal, there are plenty of bidders who will pay for epoxyed black boxes that will do decryption.<p>There's also the UPS/Fedex route - which isn't worth as much money, but you could sell them a black box that does fast routing for money.

Put up a web API that solves arbitrary SAT instances. Let other people do what they want, and I can watch while I think about what to do next.<p>Also, write a theorem prover of course, and try for big outstanding conjectures.

mariorz: is there something you'd like to tell us?

You could use it to build better compilers (compilers today have to approximate many NP-complete problems).

I've always assumed it is a given that as soon as you make that discovery, all sorts of agencies would be hunting after you and you would have to run for your life. So my worry would be how to safely publish the information to get off the hook. I used to think publishing it to Usenet and sending lots of emails would do the trick, but I am not so sure anymore.

almost is very far from done. If you have REALLY done it then probably somebody else might do it as well in the (not so) near future.<p>Also, what is the degree of the polynomial solution? If it is high then fast approximate solution might be preferable to exact slower solution (example: Simplex vs. Ellipsoid algorithms for LP) . If the solution is not linear or quadratic the most this hugely decreases your potential market.<p>If I am at such position I would look at problems for which I can beat precision/time for approximate algorithms.

If you have an algorithm with a worst case polynomial bound on the time it takes to solve an NP complete problem, then UPS, Fedex and other companies would pay nicely to use a service to optimally do scheduling, routing and resource allocation.<p>On the other hand, since it is more likely that P!=NP, this "almost" algorithm probably fails exponentially on some set of examples, and in practice there are plenty of NP complete problems which enjoy very good approximation algorithms or heuristic algorithms which work well for typical problem instances.

Ring Intel's CEO. You have the means to give him optimal layout for his CPUs saving them both massive amounts of time and more importantly space on CPUs. If you like you can also approach AMD and get the two bidding against each other.<p>They will bite your hand off and you will be a rich man.

Two monitors at the same time, friend.<p>In seriousness, I'd be careful because as others have pointed out, some crypto systems would be vulnerable.

1) Cash in your discovery for US $1 million [0].<p>2) Fund your own disruptive startup incubator, a la YCombinator (using the publicity from your discovery to attract hoards of scrappy geniuses).<p>2.5) Optionally, focus on startups that monetize P=NP - again, for publicity reasons (as well being able to leverage your own expertise in evaluating biz ideas).<p>3) Profit!<p>(profferred tongue in cheek, of course - it's not very private :)<p>[0] <a href="http://www.claymath.org/millennium/P_vs_NP/" rel="nofollow">http://www.claymath.org/millennium/P_vs_NP/</a>

Well, if you write a theorem prover, you can probably get just about every mathematical proof prize out there. That's $7 million from the Clay Institute alone...

I wondered along these lines recently. A relative is getting caught up in the "water-car", "Brown's Gas", Hydrogen internet scam.. Where you convert water to 2H2 + O2 and burn that to power the car, house, etc for "free".<p>What would you do if it actually worked? How would you convince people? Where would you share it?

solve protein folding, become evil megalomaniac with doomsday virus.

I'd write a kick-ass regular expression engine.<p><a href="http://perl.plover.com/NPC/NPC-3SAT.html" rel="nofollow">http://perl.plover.com/NPC/NPC-3SAT.html</a>

If you've got a good solution, there are plenty of systems you can make more efficient (not only salesmen and UPS :-) I would make a list, create a consultancy and propose my services to the industries with the highest remunerative potential :-)

Build a superhuman intelligence (duh).

The US government pays a million bucks per new prime right? Just push those out every week or so.

Are we answering a homework question for you? :p

Hack the planet.<p>I feel so unclean for saying that.