tag:blogger.com,1999:blog-3722233.post7911165752991397368..comments2024-07-16T20:11:35.823-05:00Comments on Computational Complexity: Should you reveal a P = NP algorithm?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-23156830038672865382021-06-01T05:54:52.243-05:002021-06-01T05:54:52.243-05:001. why P=NP needed to get bitcoins on a laptop? pe...1. 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?Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91342353682173583452018-05-11T11:23:11.745-05:002018-05-11T11:23:11.745-05:00Also I think crypto will not be affected. The cons...Also 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73523072888192742282018-05-11T11:20:45.421-05:002018-05-11T11:20:45.421-05:00How about Fields medal? Say you find this magical ...How 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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23339015259530719482018-04-16T04:42:36.549-05:002018-04-16T04:42:36.549-05:00How about Fields medal? Say you find this at 39 an...How about Fields medal? Say you find this at 39 and you are about to age out? ;)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34117764727795458262017-07-31T16:54:38.126-05:002017-07-31T16:54:38.126-05:00i believe the worst case discussed here already ha...i believe the worst case discussed here already happened .. check this : https://arxiv.org/abs/1602.04955 Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24868026298141424252014-05-08T13:42:32.977-05:002014-05-08T13:42:32.977-05:00This was what Cook-Levin was about. If you have an...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. <br /><br />This is the whole point behind NP-complete to begin with.Unknownhttps://www.blogger.com/profile/04635514928258113448noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38908799744469013192014-05-08T13:30:47.056-05:002014-05-08T13:30:47.056-05:00That's search, search is NP complete, triviall...That's search, search is NP complete, trivially reducible to SAT. It's sort of the point behind nondeterministic Turing machine oracles to begin with. Unknownhttps://www.blogger.com/profile/04635514928258113448noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43704656439362550302014-04-23T07:10:14.171-05:002014-04-23T07:10:14.171-05:00http://en.wikipedia.org/wiki/Travelling_Salesman_(...http://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79392723207172253772014-04-22T13:57:51.599-05:002014-04-22T13:57:51.599-05:00*Regressible, d'uh.*Regressible, d'uh.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58515873073608379022014-04-22T00:25:50.141-05:002014-04-22T00:25:50.141-05:00Fortunately P≠NP, good for cryptography that...
Se...Fortunately P≠NP, good for cryptography that...<br />See this rough outline on algorithmic numerical error as a scaled feed forward in a fractal hash function.<br />(Regressable with a indexing trapdoor table.)<br />http://unitambo.files.wordpress.com/2014/04/one-way-function3.pdf<br />Or try the spreadsheet, it probably makes more sense?<br />http://unitambo.wordpress.com/spreadsheet-model/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89461281573685617532014-04-18T04:56:15.136-05:002014-04-18T04:56:15.136-05:00I mean no disrespect, but this post is very naive....I 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.<br /><br />What did they do? Did they make him a tremendous job offer and offer him millions?<br /><br />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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70155209851211097882014-04-17T15:07:24.593-05:002014-04-17T15:07:24.593-05:00Great question... great response... just one issue...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14792933062810646422014-04-17T12:52:55.198-05:002014-04-17T12:52:55.198-05:00Mining refers to brute-force sifting through candi...Mining 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.Beni Cherniavsky-Paskinhttps://www.blogger.com/profile/10500835143321767281noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52418991877416496072014-04-17T09:32:05.122-05:002014-04-17T09:32:05.122-05:00but that doesn't mean that the specific techni...but 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." <br /><br />that 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 .... Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35025383953746635862014-04-17T08:56:02.287-05:002014-04-17T08:56:02.287-05:00One _mines_ bitcoins, not _mints_. (Delete at wil...One _mines_ bitcoins, not _mints_. (Delete at will.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49571656891026027522014-04-17T08:43:08.662-05:002014-04-17T08:43:08.662-05:00Could you provide a reference to a proof showing t...Could 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28311483804443230772014-04-17T08:40:01.718-05:002014-04-17T08:40:01.718-05:00This was the subject of a Fox Follies skit, if I&#...This was the subject of a Fox Follies skit, if I'm remembering correctly, in 1984 (Palm Beach), which was lead by Al Meyer.<br /><br />The 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!stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.com