4 ms·
What would you attempt if you knew P equals NP?
- thedevindevops 3y agoIf that Elementary episode is anything to go by, you join a government agency and your work becomes classified.
- mikewarot 3y agoFactoring Semiprimes to break PKI seems to be about the only thing such knowledge might be useful for.
- Someone 3y agoI don’t think you could do anything with just that knowledge. A proof of the existence of algorithm for solving NP problems in polynomial time would be better. It gets you a Ph. D., a million dollars (https://en.wikipedia.org/wiki/Millennium_Prize_Problems https://en.wikipedia.org/wiki/Millennium_Prize_Problems) and possibly tenure. An actual algorithm for solving NP problems in polynomial time would do a bit more, IF its constants would be decent.
- twright 3y agoA professor liked to point out that if you do prove P=NP you could exploit it to solve the remaining open Millennium Problems netting you a few more million dollars and historic fame. Knuth's opinion on it is that you couldn't do much with it otherwise. "Knowledge of the mere existence of an algorithm is completely different from the knowledge of an actual algorithm." [1] [1]: question 17: https://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions https://www.informit.com/articles/article.aspx?p=2213858&WT....
- ActorNightly 3y agoIf P=NP, then its pretty much a matter of throwing enough compute at a neural network to essentially compress the representation of reality into an algorithm that can run faster than reality, which means that an all powerful all knowing AGI is actually possible, which then likely means we live in a simulation already. I don't really know what I would personally do though.
- gregjor 3y agoProve once and for all the correct way to put toilet paper on the roller.