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

https://news.ycombinator.com/item?id=637002

by mariorz • 17 years ago

54 65 17 years ago

news.ycombinator.com

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?

charlesju• 17 years ago

Make my salesmen travel more efficiently?

andylei• 17 years ago

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

PStamatiou• 17 years ago

that just made my day. thank you.

embeddedradical• 17 years ago

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.

mariorz2• 17 years ago

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.

carterschonwald3• 17 years ago

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.

carterschonwald3• 17 years ago

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

zackattack• 17 years ago

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

rms• 17 years ago

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.

stcredzero• 17 years ago

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.

arjunnarayan• 17 years ago

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.

mitko2• 17 years ago

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.

mariorz2• 17 years ago

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.

mitko2• 17 years ago

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

tlrobinson2• 17 years ago

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

jules• 17 years ago

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

tolmasky• 17 years ago

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

windsurfer• 17 years ago

Errr, citation needed?

ZachPruckowski• 17 years ago

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.

dave_au5• 17 years ago

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.

bdr• 17 years ago

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.

ijt• 17 years ago

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.

donaq2• 17 years ago

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?

cjp• 17 years ago

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

jjb• 17 years ago

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.

praptak2• 17 years ago

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.

wlievens3• 17 years ago

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

cjg• 17 years ago

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?

benkant• 17 years ago

I believe I just went cross-eyed.

Monkeyget• 17 years ago

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

dave_au5• 17 years ago

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

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

rw• 17 years ago

Build a superhuman intelligence (duh).

whatusername2• 17 years ago

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?

jerf• 17 years ago

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.

whatusername2• 17 years ago

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)

redsymbol• 17 years ago

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/

nazgulnarsil• 17 years ago

solve protein folding, become evil megalomaniac with doomsday virus.

dave_au5• 17 years ago

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

sown3• 17 years ago

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.

dave_au5• 17 years ago

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

sown3• 17 years ago

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

philwelch• 17 years ago

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

tlrobinson2• 17 years ago

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.

carterschonwald3• 17 years ago

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.

joshu• 17 years ago

I quite enjoyed this book, actually.

thalur• 17 years ago

Sounds like something Dan Brown would write.

astrodust• 17 years ago

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.

lacker• 17 years ago

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

ca98am79• 17 years ago

This can't possibly be the best suggestion.

Tichy• 17 years ago

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.

dinkumthinkum• 17 years ago

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.

dave_au5• 17 years ago

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

msie• 17 years ago

Are we answering a homework question for you? :p

HouseTrip• 17 years ago

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

andreyf2• 17 years ago

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

praptak2• 17 years ago

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

wlievens3• 17 years ago

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

jdoliner• 17 years ago

Ahem, 6 million Poincare Conjecture was claimed.

PKeeble• 17 years ago

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.

wlievens3• 17 years ago

Please call ARM and its Si partners first. Thanks.

babycakes• 17 years ago

Hack the planet.

I feel so unclean for saying that.

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

Related Stories