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?
69 comments
[ 2.7 ms ] story [ 126 ms ] threadif 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.
I like your plan for dealing with academia.
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.
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.
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.
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.
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.
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.
This seems to be related: http://en.wikipedia.org/wiki/P_%3D_NP_problem#Consequences_o...
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.
Also, write a theorem prover of course, and try for big outstanding conjectures.
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.
-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! :)
http://perl.plover.com/NPC/NPC-3SAT.html
What would you do if it actually worked? How would you convince people? Where would you share it?
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.
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)
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/
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 :)
In seriousness, I'd be careful because as others have pointed out, some crypto systems would be vulnerable.
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 :)
So...should I look for a literary agent or try and bootstrap this myself by hiring a private press? ;)
Yours sounds good too.
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 imagine such a thing involves a lot of extreme refactoring, hot plugging, and something with an obscene amount of command line action.