You could use it to build better compilers (compilers today have to approximate many NP-complete problems).
Ask HN: P=NP, what do you do?
11–20 of 70 posts
Re: Ask HN: P=NP, what do you do?
#12almost 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 m…
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.
Re: Ask HN: P=NP, what do you do?
#13The US government pays a million bucks per new prime right? Just push those out every week or so.
Re: Ask HN: P=NP, what do you do?
#14If 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 com…
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.
Re: Ask HN: P=NP, what do you do?
#15The US government pays a million bucks per new prime right? Just push those out every week or so.
Errr, citation needed?
Re: Ask HN: P=NP, what do you do?
#16let 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'…
[deleted]
Re: Ask HN: P=NP, what do you do?
#17Answer 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.
Re: Ask HN: P=NP, what do you do?
#18almost 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 m…
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...
Re: Ask HN: P=NP, what do you do?
#19mariorz: is there something you'd like to tell us?
[deleted]
Re: Ask HN: P=NP, what do you do?
#20Put 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.