6 ms·
Ask HN: P=NP, what do you do?
Imagine you are a reclusive scientist genius who after spending the last 15 years exploring the space of algorithms for solving 3SAT, has stumbled upon a fast polynomial-time solution.
Somewhat tired as you are of the academic community, and not very interested in prizes or distinctions, you decide it would be in your
best interest to try to monetize your discovery privately. To this purpose, what massively lucrative applications can you think of for such an algorithm?
- PKeeble 17y agoRing 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. They will bite your hand off and you will be a rich man.
- wlievens 17y agoPlease call ARM and its Si partners first. Thanks.
- charlesju 17y agoMake my salesmen travel more efficiently?
- andylei 17y agonot that much more efficient. approximation algorithms provide pretty good solutions.
- PStamatiou 17y agothat just made my day. thank you.
- embeddedradical 17y agolet 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. 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.
- deleted 17y ago[deleted]
- mariorz 17y agoThe problem with this is it's somewhat public. Assuming your system was outstandingly good, could it not raise dangerous suspicions? I like your plan for dealing with academia.
- carterschonwald 17y agoIf 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. 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.
- carterschonwald 17y agoand if you in fact have a problem that shows P=NP, publish it so you can win the millenium prize, 1 million dollars plus ease at getting tenure so you can goof off is nothing to sneeze at
- zackattack 17y agoEven though the millenium prize may be the most obvious solution, your best option might be to monetize the discovery privately.
- neilc 17y agoAssuming that your solution is practical, which might well not be the case (O(n^c) is polynomial for any constant c).
- rms 17y agoBid 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. 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.
- stcredzero 17y agoWho 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 Post it very publicly in many places, including 4chan. Hope that Anonymous gets hold of it, or that the spooks start whacking /b/tards or the /b/tards start whacking the spooks.
- arjunnarayan 17y agoYou 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. 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.
- mitko 17y agoalmost 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. 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. If I am at such position I would look at problems for which I can beat precision/time for approximate algorithms.
- mariorz 17y agoI've edited out "almost", I meant to use it as qualifying the "stumbled upon" part, not the algorithm. In any case by fast polynomial solution I meant one with a low degree. Let's assume this algorithm is as fast as existing approximate ones.
- mitko 17y agook then. This shifts the hard part of the problem from "how do I make this run in a lifetime", to "how do I reduce this problem to 3SAT efficiently". This seems to be related: http://en.wikipedia.org/wiki/P_%3D_NP_problem#Consequences_of_proof http://en.wikipedia.org/wiki/P_%3D_NP_problem#Consequences_o...
- tlrobinson 17y agomariorz: is there something you'd like to tell us?
- deleted 17y ago[deleted]
- jules 17y agoYou could use it to build better compilers (compilers today have to approximate many NP-complete problems).
- tolmasky 17y agoThe US government pays a million bucks per new prime right? Just push those out every week or so.
- windsurfer 17y agoErrr, citation needed?
- ZachPruckowski 17y agoIgnoring the fact that no one has heard of this "Million bucks a prime" program, if P = NP, then the government doesn't need primes, as prime-factoring-based crypto is dead.
- dave_au 17y agoAnswer from Cook: www.cs.toronto.edu/~sacook/homepage/JACMpvsnp.ps 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 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. So you can go from P-time checkable constraints to P-time enumeration of things which fill the constraints.
- bdr 17y agoPut 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. Also, write a theorem prover of course, and try for big outstanding conjectures.
- ijt 17y agoTest 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.
- donaq 17y agoWouldn't writing a complete test suite take equivalent effort to writing the program in the first place? I mean, wouldn't they require the same amount of information? Then, to simplify the task of writing test suites, you might want to design a programming language that compiles into test suites, but would you use your program-writing program to write the program that describes the test suite? And also, who watches the watchers?
- cjp 17y agoIt's turtles. Turtles I say. Turtles all the way down!
- jjb 17y agoThe test suite will describe the desired behavior, regardless of all other dimensions. The P=NP optimizer/generator will then generate an implementation that is optimal along one or more dimensions (like space or time efficiency). Also-- regardless of that, It's "easier" in several senses to describe the desired behavior of an API than to implement that API. Let's say we wanted to implement addition for a calculator. Here's a complete description: -1 is the lowest number -successor(N) is the successor to number N That's a complete description of the natural number system, but it's not a useful addition function in any sense.
- donaq 17y agoLet's say we wanted to implement addition for a calculator. Here's a complete description: -1 is the lowest number -successor(N) is the successor to number N In the first place, that is not a complete description of natural numbers. Natural numbers have to be integers. So if you're going to tell a computer program that "1 is the lowest number", you'd first have to tell it what you mean by "number" and "lowest". Also, "successor(N) is the successor to number N"? That seems rather meaningless. What is "successor" in the first place? If your generator already knows what "successor" means, why do you have to describe it again? If the generator doesn't know what "successor" means, why are you using it in your description of a successor function? That's a complete description of the natural number system, but it's not a useful addition function in any sense. Even assuming your description was complete, why would a description of the set of natural numbers imply the creation of an addition function? Unless we're talking about a code generator that reads minds! :)
- dave_au 17y agoI'd write a kick-ass regular expression engine. http://perl.plover.com/NPC/NPC-3SAT.html http://perl.plover.com/NPC/NPC-3SAT.html
- rw 17y agoBuild a superhuman intelligence (duh).
- whatusername 17y agoI 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". What would you do if it actually worked? How would you convince people? Where would you share it?
- jerf 17y agoConvincing people is easy. Build a closed system, grab an inverter, sell power back to the power company, which in many places they are required by law to pay you for. Sell enough power back, you'll get attention. The idea that demonstrating a net-positive process is hard is merely smokescreen tossed up by the perpetual motion scamsters. It's not. It's easy. It's as easy as it is to demonstrate that a gas generator produces power when you add gasoline and oxygen to the system. If you have a process that works, you can generate and sell power to prove your point and go from there. The fact that nobody can quite seem to manage this feat, despite the easy money it would represent if you actually had a solution, is proof enough that it simply doesn't work. A system that pushed out a kilowatt and never stopped would be very easy to prove. It's only hard to prove something when you're sitting there fiddling with picowatts and arguing whether the power comes from the magic process or if you're simply translating magnetism into electricity or some other fiddly, on-the-edge-of-rounding-error sort of thing. Also, any true net-positive process can be turned into this sort of thing, simply by feeding back the net-positive process onto itself. Any net-positive process should be able to produce a kilowatt, easily. (Arbitrary amounts of power, actually, but let's take something thinkably-small.) Again, the fact that they have to resort to fiddly little rounding errors is proof that they have nothing. Any interesting perpetual motion process would be able to power a nation, if it actually worked.
- whatusername 17y agoOh I agree. And the existence of China (very large state with low regard for IP law and very significant energy requirements) is proof enough that the "energy companies are suppressing this" myth is a farce. But even if I had that kind of proof - I would suggest you'd still think I was a crack-pot. It would be a very very significant uphill battle to gain acceptance in the science community. (obviously - as I would have experimental proof that a whole bunch of science theory is wrong)
- redsymbol 17y ago1) Cash in your discovery for US $1 million [0]. 2) Fund your own disruptive startup incubator, a la YCombinator (using the publicity from your discovery to attract hoards of scrappy geniuses). 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). 3) Profit! (profferred tongue in cheek, of course - it's not very private :) [0] http://www.claymath.org/millennium/P_vs_NP/ http://www.claymath.org/millennium/P_vs_NP/
- nazgulnarsil 17y agosolve protein folding, become evil megalomaniac with doomsday virus.
- dave_au 17y agoI thought protein folding was harder than NP. IIRC, calculating the free energy of a molecule is in #P (count the number of solutions to a problem in NP), and you still need to step it through time or otherwise deal with the actual folding bit. I might be remembering incorrectly though. Edit: http://en.wikipedia.org/wiki/Sharp-P-complete http://en.wikipedia.org/wiki/Sharp-P-complete Also: whoops - looks like structure prediction can be done with high accuracy in NP - just don't try to animate it :)
- sown 17y agoTwo monitors at the same time, friend. In seriousness, I'd be careful because as others have pointed out, some crypto systems would be vulnerable.
- dave_au 17y agoMore than some, I think. Most strong crypto short of one-time pads makes use of NP (or at least problems solvable by NP problems, factoring is probably a little easier than NP). NP is nice for crypto since it has P time checkable solutions - so just make the "password" an encoding of the solution and you're golden. It's easy to check that a password is correct, and it takes EXP time to brute force. Hopefully the crypto implementation blocks IPs after some number of login attempts that is less than EXP :)
- sown 17y agoI'm reminded from the seminal hacker movie: "There's not a government on this earth that wouldn't kill us all for that thing."
- philwelch 17y agoI've always thought that this would make a great plot for a science fiction novel. A computer science 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. So...should I look for a literary agent or try and bootstrap this myself by hiring a private press? ;)
- tlrobinson 17y agoThere's Sneakers (http://www.imdb.com/title/tt0105435/ http://www.imdb.com/title/tt0105435/) but that's just about factoring large numbers, and is pretty light on the CS (though Len Adleman, the "A" in "RSA", was a consultant on that film). Yours sounds good too.
- carterschonwald 17y agoSomeone already did this http://en.wikipedia.org/wiki/The_Atrocity_Archives http://en.wikipedia.org/wiki/The_Atrocity_Archives basically, all the really clever computer science such as NP=P turns out to involve summoning demons etc in the book. If you want to read a ridiculous spin on computer science + fantasy, fun read.
- joshu 17y agoI quite enjoyed this book, actually.
- thalur 17y agoSounds like something Dan Brown would write.
- astrodust 17y agoThis isn't a real genre of book until there's computer science fiction fanfiction. I imagine such a thing involves a lot of extreme refactoring, hot plugging, and something with an obscene amount of command line action.
- deleted 17y ago[deleted]
- lacker 17y agoI would post a question on HN saying "P=NP, what do you do?" and then take the best suggestion.
- ca98am79 17y agoThis can't possibly be the best suggestion.
- Tichy 17y agoI'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.
- dinkumthinkum 17y agoYou could go low-tek and print off hundreds of copies and have them post all over universities, physically mailed to people, etc and then blasted on YouTube, and so forth.
- dave_au 17y agoYou could conceivably ssh into anything, so you could just leave copies _everywhere_.
- msie 17y agoAre we answering a homework question for you? :p
- deleted 17y ago[deleted]
- HouseTrip 17y agoIf 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 :-)
- andreyf 17y agoWell, 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...
- babycakes 17y agoHack the planet. I feel so unclean for saying that.