tag:blogger.com,1999:blog-3722233.post7769490753053513896..comments2024-04-19T18:30:53.405-05:00Comments on Computational Complexity: The Probability of P=NPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-3722233.post-33573010804815882942017-10-08T18:07:41.394-05:002017-10-08T18:07:41.394-05:00A better question is: What's the probability o...A better question is: What's the probability of there not to be a solution to the P vs. NP problem? In other words, what's the probability that the problem is unsolvable?Anonymoushttps://www.blogger.com/profile/10363727269601019533noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85207093461408925142009-12-07T09:09:41.837-06:002009-12-07T09:09:41.837-06:00Robin, someone can refuse your bet, without reveal...Robin, someone can refuse your bet, without revealing any useful information about their belief in P vs. NP.<br /><br />A Bayesian agent must be logically omniscient; they have a probability of one or zero for all purely logical sentences, depending on whether they are either true or false. If someone is not able to ascribe such beliefs to logical statements, then they are not a Bayesian agent, by definition. <br /><br />If they are not a Bayesian agent, then you cannot equate their degrees of belief with their propensity to bet, precisely because Dutch books exist against them -- their beliefs actually are (formally) incoherent.<br /><br />In short, you can't use an argument which relies on the deductive closure of beliefs to reason about beliefs which are in fact not deductively closed.Neel Krishnaswamihttps://www.blogger.com/profile/06853898957395028131noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37522487206564484852009-12-05T17:27:47.668-06:002009-12-05T17:27:47.668-06:00I'm not sure that scientific betting markets h...I'm not sure that scientific betting markets hold up when it comes to propositions that, if true, would completely change the way we understand the world. The utility of those propositions is effectively infinite, since they would require reformulating all of our existing utility functions in ways that we can't even comprehend. Therefore it is rational to accept any bet on that proposition short of the entire universe being destroyed---implying a personal probability 0 of the truth of that proposition. <br /><br />I submit that P=NP is one of those propositions, and that Lance is therefore being entirely rational in giving it zero probability.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-680743780823120402009-12-05T13:20:31.211-06:002009-12-05T13:20:31.211-06:00The utility of a penny may be zero or even negativ...The utility of a penny may be zero or even negative, but what about the utility of P=NP? Do you think all of Lance's possessions have greater utility to Lance than a polynomial-time algorithm for 3SAT?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47557865811109242382009-12-04T23:48:02.613-06:002009-12-04T23:48:02.613-06:00I wouldn't take Robin Hanson's bet if he w...I wouldn't take Robin Hanson's bet if he were betting that over the integers 1+1 equals 3. My utility of a penny (and I suspect Lance's as well) is effectively 0; it might even have a -ve utility to me since pennies are annoying to deal with. <br /><br />What about a bet with a one in a trillion chance via RAND() that Robin gives Lance everything he has if P!=NP. Should Lance take that bet? In expectation it might be similar but at least there is no questioning the utility to Lance.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61785655812619322402009-12-04T22:41:59.984-06:002009-12-04T22:41:59.984-06:00I bet Lance would take Robin's bet.I bet Lance would take Robin's bet.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29852105690309351162009-12-04T20:19:55.417-06:002009-12-04T20:19:55.417-06:00Here's the deal. If it is proved P=NP you giv...Here's the deal. If it is proved P=NP you give me absolutely everything you have. If it is proved otherwise, you run RAND() for a one in a million chance and if that happens I give you a penny. Deal? If not, your P is *not* zero.Robin Hansonhttp://overcomingbias.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7048807456453569952009-12-04T19:51:38.701-06:002009-12-04T19:51:38.701-06:00What are the odds on: P vs NP is solved. Don'...What are the odds on: P vs NP is solved. Don't be shy.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26104939817834326102009-12-04T15:12:22.602-06:002009-12-04T15:12:22.602-06:00Well, this bet "P vs NP" is too expansiv...Well, this bet "P vs NP" is too expansive "1 million $" for that. <br /><br />But what about:<br /><br />(*) Multiplying two numbers is more difficult (requires at least log n more operations) than adding them? <br /><br />Folks, I do not understand why we stick on "P vs NP" and the like, when we have more urge problems?<br /><br />Just because we cannot approach them with "oracles" or similar?<br /><br />I would bet for P!=NP, of course, but I would be much happier in a P=NP world. Then the questions, like (*) above, would attract more brains.Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1739303081733583392009-12-04T11:54:03.443-06:002009-12-04T11:54:03.443-06:00well, that's not the story that anon was talki...well, that's not the story that anon was talking aboutAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19763775693967189382009-12-04T11:34:40.970-06:002009-12-04T11:34:40.970-06:00Of course, P != NP with probability 1 -- relative ...Of course, P != NP with probability 1 -- relative to a random oracle. <br /><br />Bennett and Gill Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31063913078604452932009-12-04T11:22:31.928-06:002009-12-04T11:22:31.928-06:00oh you mean the gold bet ? yeah, that's quite ...oh you mean the gold bet ? yeah, that's quite a thing. please tell us! please!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25295228106246408712009-12-04T11:19:10.523-06:002009-12-04T11:19:10.523-06:00lancie, lancie, lancie, why don't you tell the...lancie, lancie, lancie, why don't you tell the story of your advisor ? I think that's worth an interesting read.whynotnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38285779963063307942009-12-04T10:02:49.161-06:002009-12-04T10:02:49.161-06:00I think the last few comments have clarified the i...I think the last few comments have clarified the issue. So, to get some quantitative data after all, let's rephrase the question: "Lance, which one is more horrific and unbelievable: a) P = NP or b) Your loved one is alien ax murderer ?" Yes, we might need some follow-up questions.Wim van Damhttps://www.blogger.com/profile/14484831637730978511noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40750812848294173032009-12-04T10:02:40.919-06:002009-12-04T10:02:40.919-06:00> To the Bayesians who cannot understand Lance&...> To the Bayesians who cannot understand Lance's answer<br /><br />To the theorists who cannot understand Dean Foster's question:<br /><br />There are many of us who are not experts in theory, have never thought seriously about how to prove or disprove P=NP, but still have an interest in the problem, maybe even working on approximate approaches to NP hard problems on a daily basis. We clearly can't expect a yes or no answer, but we're very interested to know how close to one side or the other the experts think we are. The question is a very reasonable way to get at the answer*.<br /><br />We're supposed to be scientists--I would hope that we can separate our personal hopes and biases from our objective interpretations of the evidence. Answering seriously would help us better understand your field. <br /><br />For the alien axe murderer crowd, help us out. Do you think it more likely that your loved one is an alien axe murderer or that P=NP? Is it more likely that your loved one is just a murderer or that P=NP? Give us some perspective, please.<br /><br />* [rant] The evidential (or Bayesian) interpretation of probability is not an obscure notion reserved only for the "crazy Bayesians", and refusing to acknowledge it by claiming one only subscribes to the frequency view of probability is pretty elementary (<a href="http://en.wikipedia.org/wiki/Probability_interpretations" rel="nofollow">http://en.wikipedia.org/wiki/Probability_interpretations</a>)[/rant]Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48377014346532514442009-12-04T08:52:40.877-06:002009-12-04T08:52:40.877-06:00Alien ax murderer comment: Hilarious and spot on....Alien ax murderer comment: Hilarious and spot on.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69905256735102736512009-12-04T08:32:59.863-06:002009-12-04T08:32:59.863-06:00In my naiive understanding of this post, maybe Lan...In my naiive understanding of this post, maybe Lance just wants to say he much wishes P = NP not to be true.<br />The probablity is more refered to belief in one's heart instead of real measure or proof...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77534497432233595552009-12-04T08:32:50.016-06:002009-12-04T08:32:50.016-06:00To the Bayesians who cannot understand Lance's...To the Bayesians who cannot understand Lance's answer: It's a bit like being asked "What's the probability that your loved one is an alien axe murderer?" There's obviously a non-zero probability for this event, but some of us can't bring ourselves to assign a non-zero probability to this event. <br /><br />Don't take the Pr(P=NP)=0 statement at face value and start quoting Bayes theorem, Robin Hanson or Eliezer Yudkowsky.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12036605597621111692009-12-04T07:49:02.287-06:002009-12-04T07:49:02.287-06:00... Either you assigned an initial belief of 0 to ...... Either you assigned an initial belief of 0 to the proposition, before you even learned anything about it, or you managed to obtain infinitely strong evidence against it.<br /><br />If neither of these, you are using something other than probabilities. "I can't find it in my heart..." hints at that.<br /><br />Note that actually assigning probability zero means that if it actually does turn out P = NP, you would be unable to believe it even IF you saw and understood the proof. Even if the proof actually was constructive, gave an implementation of an algorithm that worked, and that you could easily test its ability to do stuff like crack just about any (non One-Time-Pad equivalent) crypto, ask of a particular mathematical proposition or its negation has a poof of length N or less, etc etc...<br /><br />Even so, you would have to instead conclude you were hallucinating it all, or your ability to reason from that to the ability to evaluate the validity was flawed, etc... In other words, by assigning probability zero, you are effectively saying "no matter what, I am forbidden from ever admitting error on this matter" (assuming one's actually following the rules of probability)<br /><br />oh, martinschwarz: Actually, pretty much all crypto other than one time pads is dependent on P != NP.<br /><br />That is, other than stuff encoded via an OTP, one can generally tell the difference between a successful and non successful decryption, right? And do so in polynomial time. (For example, a successful decryption of english text looks like, well, english text. Has english words, syntax, etc...)<br /><br />So being able to crack NP complete stuff would break pretty much anything not equivalent to a one time pad.<br /><br />(oh, incidentally, there're some public key cryptosystems that seem to be able to survive the existence of a quantum computer, but not P = NP (well, okay, I guess if the exponent is high enough, then... but you know what I mean))Unknownhttps://www.blogger.com/profile/16683981206948128996noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10243054473749320172009-12-04T07:29:42.624-06:002009-12-04T07:29:42.624-06:00Every use of public-key cryptography bets on P!=NP...Every use of public-key cryptography bets on P!=NP (and quantum computers not being built) over the period of time the encrypted information is considered relevant. There are even <a href="http://www.keylength.com/" rel="nofollow">websites</a> suggesting secure key lengths based on an estimation of a secure time-period during which keys of the suggested length should be secure. Of course these suggestions are only based on extrapolitions of Moore's law, but essentially, they also implicitly bet on P!=NP and QCs not existing. So, in fact, the bet that is being asked for has already been taken: just check what is the most valueable piece of encrypted information, that if cracked would be of serious financial value to the attacker. For example, a recent log of an SSL encrypted session of let's say Bill Gates accessing his bank account over the Internet would mean, that Bill Gates had implicitly accepted the bet of P!=NP and QC not existing with the current balance of his account.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7205138715693954362009-12-04T06:50:56.243-06:002009-12-04T06:50:56.243-06:00I find this dispute very odd. Robin Hanson ages ag...I find this dispute very odd. Robin Hanson ages ago came up with explanations as to why betting in science is a good idea. http://hanson.gmu.edu/gamble.html<br /><br />There are loads of prediction markets in science already. http://www.ideosphere.com/fx-bin/Claim?claim=CFsn<br /><br />Now the futures in p=Np have to be set at some point int hte future. You could say "will P=NP be proven disproven by 2100" and the bets could change hands by our descendants. there are many long term financial risks that are traded like this.<br /><br />suppose you come up with a proof that makes it less likely P=NP. Not proves it but just makes it less likely. The current odds are 1000 to 1 that someone will prove p=np by jan 1st 2100. You think that your proof will move the odds out to 2000 to 1. You would be a fool not to short P=NP bets and then reap a profit on the maths futures prediction market when your proof comes out.Iamreddavehttps://www.blogger.com/profile/02768287658329807075noreply@blogger.com