A reader asks
What would you do if you could prove that P=NP with a time-complexity of n2 or better... moreover, would you publish it?
There are all these statements of the good that could come of it. But how would the government react in its present state? Would it ever see the light of day? How would a person be treated if they just gave it away on the internet? Could a person be labeled a threat to national security for giving it away?I consider this a completely hypothetical and unlikely scenario. If you think this applies to you, make sure you truly have a working algorithm. Code it up and mint yourself some bitcoins, but not enough to notice. If you can't use your algorithm to mint a bitcoin, you don't have a working algorithm.
The next step is up to you. I believe that the positives of P v NP, like their use in curing diseases for example, greatly outweigh the negatives. I would first warn the Internet companies (like was done for heartbleed) so they can modify their systems. Then I would just publish the algorithm. Once the genie is out of the bottle everyone can use it and the government wouldn't be able to hide it.
If you can find an algorithm so can others so you should just take the credit or someone else will discover it. I don't see how one can get into trouble for revealing an algorithm you created. But you shouldn't take legal advice from this blog.
Once again though no one will take you seriously unless you really have a working algorithm. If you just tell Google you have an algorithm for NP-complete problem they will just ignore you. If you hand them their private keys then they will listen.
This was the subject of a Fox Follies skit, if I'm remembering correctly, in 1984 (Palm Beach), which was lead by Al Meyer.
ReplyDeleteThe skit imagined a theoretician presenting themselves to the CIA. There's a brief discussion between CIA types: "Yet another one." "We'll hire him as usual." "Budget cuts." Bang!
http://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film)
DeleteCould you provide a reference to a proof showing that SHA-256 is NPC or showing that if you solve P=NP that takes you right to a solution for reversing SHA-256.
ReplyDeleteThat's search, search is NP complete, trivially reducible to SAT. It's sort of the point behind nondeterministic Turing machine oracles to begin with.
DeleteOne _mines_ bitcoins, not _mints_. (Delete at will.)
ReplyDeleteMining refers to brute-force sifting through candidates but that assumes it's a hard problem; if NP is easy for you, you should be able to print valid coins at will - so I find "mint" very apt here.
Deletebut that doesn't mean that the specific technique she found for the n^2 reduction works for the bitcoin algorithm. lance, it seems u r diving into the same pitfall that u once detected when watching the show on TV called numbers. Recall the dialogue when one them said (i think they were under time pressure) ... "if we knew that p=np, then we could easily hack this or that or generate this quick algorithm."
ReplyDeletethat being said, it would be nice to have this little problem of the century resolved once and for all. how many papers are there that claim p=np again ? someone used to have a list ....
This was what Cook-Levin was about. If you have an O(n^2) SAT you can get any NP-complete algorithm with no more than O(n^7) or so. You reduce your problem to SAT, with Cook-Levin as a guide, and then run your SAT solver.
DeleteThis is the whole point behind NP-complete to begin with.
Great question... great response... just one issue that stands out. What if the person just found a way to solve a specific np-problem that were a game like soduko (and this person is a kid using a piece of paper or even a spreadsheet). While it has been shown the np-problems can be converted to other np-complete problems. This does not mean the kid who discovered the algorithm has other programming skills. In this instance, the response assumes the user has computer hacking skills. The discovery would then be subject to the kid learning new skills before another person with the said skillset can. Therefore, a working algorithm can exist... without minting bitcoins or an equivalent means of ill-gotten credits. This would imply the algorithm would be in a state of limbo, if no-one took the kid seriously. Or, the kid would be subject to trusting someone who had the skills to go the final mile.
ReplyDeleteI mean no disrespect, but this post is very naive. In France, we have the famous precedent of Serge Humpich, who found a flaw in the credit card system. He tried negotiating with the banks but they would not believe him. So he bought a single metro ticket with a false credit card.
ReplyDeleteWhat did they do? Did they make him a tremendous job offer and offer him millions?
Of course not, they just prosecuted him, put him in jail and did not change *anything* about their security system. Would google react differently if you handed them their private keys? Are you willing to risk your life on their good faith?
Fortunately P≠NP, good for cryptography that...
ReplyDeleteSee this rough outline on algorithmic numerical error as a scaled feed forward in a fractal hash function.
(Regressable with a indexing trapdoor table.)
http://unitambo.files.wordpress.com/2014/04/one-way-function3.pdf
Or try the spreadsheet, it probably makes more sense?
http://unitambo.wordpress.com/spreadsheet-model/
*Regressible, d'uh.
ReplyDeletei believe the worst case discussed here already happened .. check this : https://arxiv.org/abs/1602.04955
ReplyDeleteHow about Fields medal? Say you find this at 39 and you are about to age out? ;)
ReplyDeleteHow about Fields medal? Say you find this magical algorithm at 39 and you are about to age out? Money or fame what do you think is better? You really cannot have both in this situation right?
ReplyDeleteAlso I think crypto will not be affected. The constants could be large and the algorithm could be cubic or higher. We can just go ahead increase RSA to 1Mbit keys. So P=NP implies internet dies is not true.
ReplyDelete1. why P=NP needed to get bitcoins on a laptop? perhaps there is a sneakier algorithm? 2. why should a P=NP algorithm be helpful? sha256 is pretty intricate compared to factoring. perhaps factoring is an easier evidence and why should breaking product of two primes be similar in practical complexity to breaking product of O(loglog N)$ primes where $log N$ is number of bits in each prime?
ReplyDelete