Hacker News new | past | comments | ask | show | jobs | submit login
Ask HN: P=NP, what do you do?
54 points by mariorz on June 1, 2009 | hide | past | favorite | 65 comments
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?




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.

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.


The 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.


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.

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.


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

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.


Answer 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.


I'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? ;)


Someone already did this 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.


I quite enjoyed this book, actually.


There's Sneakers (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.


Sounds like something Dan Brown would write.


This 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.


Make my salesmen travel more efficiently?


not that much more efficient. approximation algorithms provide pretty good solutions.


that just made my day. thank you.


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.


Wouldn'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?


It's turtles. Turtles I say. Turtles all the way down!


The 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.


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

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! :)


One important thing about TDD, in my view, is that you have two separate descriptions (the test and the code) that agree. If you get your code generated from your tests then how do you detect bugs in your tests?


I believe I just went cross-eyed.


This would probably produce a program that cheats a lot. Perhaps not by simply hardcoding the answers to the tests, but by finding a good compressing function for the set of (input, output) pairs in the test. I bet this would seldom provide the expected answers on inputs not covered by the tests.


I second this. Overfitting can be a problem even in human-written test scenario's. Usually overconfidence in your test suite is a cause.


Or writing a formal specification which would resolve the problems mentionned in the sibling comments.


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


This can't possibly be 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.

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.

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.


You 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.


You could conceivably ssh into anything, so you could just leave copies _everywhere_.


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.

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.


I'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.


ok 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_o...


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.

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.


and 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


Even though the millenium prize may be the most obvious solution, your best option might be to monetize the discovery privately.


Assuming that your solution is practical, which might well not be the case (O(n^c) is polynomial for any constant c).


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.

They will bite your hand off and you will be a rich man.


Please call ARM and its Si partners first. Thanks.


Two monitors at the same time, friend.

In seriousness, I'd be careful because as others have pointed out, some crypto systems would be vulnerable.


More 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 :)


I'm reminded from the seminal hacker movie: "There's not a government on this earth that wouldn't kill us all for that thing."


Which movie would that be?


Sneakers. :) http://en.wikipedia.org/wiki/Sneakers_(film) Decent flick.


1) 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/


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...


Just make sure that you publish the proof for P=NP last, otherwise others could beat you to it :)


Not really, anyone could use your prover to prove P=NP. It's Pandora's box!


Ahem, 6 million Poincare Conjecture was claimed.


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".

What would you do if it actually worked? How would you convince people? Where would you share it?


Convincing 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.


Oh 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)


solve protein folding, become evil megalomaniac with doomsday virus.


I 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 Also: whoops - looks like structure prediction can be done with high accuracy in NP - just don't try to animate it :)


I'd write a kick-ass regular expression engine.

http://perl.plover.com/NPC/NPC-3SAT.html


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.


Errr, citation needed?


Ignoring 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.


Are we answering a homework question for you? :p


Hack the planet.

I feel so unclean for saying that.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: