12 ms·
The Scientific Case for P≠NP
- amelius 9y agoNice post, but he loses sympathy with me for shaming that guy.
- throwaway8537 9y agoNormally I would agree, but it should be noted that Lubos is a major asshole, and deserves every bit of shaming he gets. He's easily in the top 3 biggest assholes I've had to deal with in my academic career, and that's saying something. He has it all: extreme levels of arrogance, narcissism, pedantry, absolute lack of empathy, extreme aggressivity. He is also a notable science denialist: climate change denier, evolution denier...
- bc__ 9y agoMany academics have all of that, but they sugarcoat it in polite language and less obvious backstabbing. I prefer if someone is direct.
- amelius 9y agoCould be. But how difficult is it to just ignore him, or if there is such an urge, write in a way that subtly addresses him while other readers have no clue of what is going on, or use phrases such as "some people say ..."? Plenty of good options, if you ask me.
- naasking 9y agoYou're missing the history where Lubos was spamming Aaron's other articles on these topics with all of the claims that Aaron deconstructs in this post. Readers of Aaron's blog were rightly confused about what to think. This post is the proper response to help your readers make sense of this.
- evanb 9y ago"Scott", or "Aaronson", but not "Aaron".
- throwaway8537 9y agoNothing wrong with politely pushing back against assholes. We should not tolerate behavior like Lubos' in civilized society.
- mixedmath 9y agoThis is from 2014. In this post, Scott describes various reasonings why one might consider that lead one to suspect that P!=NP. A surprising amount of verbiage of this post is devoted towards responding to/shaming a particular person who used to comment frequently on Scott's blog, and who thinks it is not safe to assume that P!=NP. I find this off-putting. But sometimes people engage in mini-crusades on the internet... the interested reader can read the prequel and subsequent exchanges between Scott and Lubos throughout comment sections of a number of blogs.
- acqq 9y agoHe does no shaming. If you claim that, you have to quote his words with which he does that, and I believe it will be obvious that your statement is biased. He responds, and explains why: "Anyway, my goal here was never to convince Luboš. I was writing, not for him, but for my other readers: especially for those genuinely unfamiliar with these interesting issues, or intimidated by Luboš’s air of certainty. I felt like I owed it to them to set out, clearly and forcefully, certain facts that all complexity theorists have encountered in their research, but that we hardly ever bother to articulate."
- mjburgess 9y agoYou can sympathize with the sentiment of the article, but there is a preoccupied ("shaming"?) quality in places that moves this from an article about P/NP to an article about showing-up a person who believes something about P/NP. Perhaps they needed to be shamed? Who knows. But it is transparent... Quoting: At one point in his post, Luboš actually compares computer scientists who find P≠NP a plausible working hypothesis to his even greater nemesis: the “climate cataclysmic crackpots.” (Strangely, he forgot to compare us to feminists, Communists, Muslim terrorists, or loop quantum gravity theorists.) Even though the P versus NP and global warming issues might not seem closely linked, part of me is thrilled that Luboš has connected them as he has. If, after seeing this ex-physicist’s “thought process” laid bare on the P versus NP problem—how his arrogance and incuriosity lead him to stake out a laughably-absurd position; how his vanity then causes him to double down after his errors are exposed—if, after seeing this, a single person is led to question Lubošian epistemology more generally, then my efforts will not have been in vain. Anyway, now that I’ve finally unmasked Luboš
- lokerfoi 9y agoWhat made me realize that P?=NP is not that important for practical issues is the unbelievable effectiveness of heuristics. They seem to get extremely close to the optimum than best approximation algorithm known for the problem.
- bbatha 9y agoUnfortunately complexity theorists have studied heuristics as well. If our heuristics are actually good we effectively solve P=NP, therefore there is a strong upper bound to our heuristics. Though the jury is still out as to whether that bound matters for practical purposes.
- fpoling 9y agoHeuristics may only work for practical values of n when the answer to P?NP may not be applicable.
- lorenzhs 9y agoThat's not entirely true. I'm a PhD student in theoretical computer science and some of my colleagues work on (hyper-)graph partitioning, both of which are NP-complete. For most real-world instances, nobody has any clue what the optimum cut/imbalance/... is. It would be very useful to evaluate the quality of the heuristics, though. A 0.5% improvement is suddenly much more impressive if you can show that you're only half as far from the optimum as your closest competitor. Or are you not seeing any improvement on instance X because whatever you're trying isn't working, or is it because you've already got the optimum?, etc
- naasking 9y agoWhat's your take on this recent work? https://www.reddit.com/r/compsci/comments/78yx99/171009278_evidence_of_an_exponential_speedup_in/ https://www.reddit.com/r/compsci/comments/78yx99/171009278_e...
- lokerfoi 9y agoOne of the best public examples is LKH solver for travelling salesman. I'm not familiar with problems for which proving optimality of a solution to a specific problem instance is not accomplished. For example, for travelling salesman and vehicle routing there are many instances with known optimum. Even for those unknown tight bounds are easily achieved.
- SomeStupidPoint 9y ago> Because, like any other successful scientific hypothesis, the P≠NP hypothesis has passed severe tests that it had no good reason to pass were it false. Is this the crux of the post? That seems like an extremely crap reason to believe a mathematical theorem. What am I missing? I also don't find his heuristic convincing -- to the point his description is making me question if P=NP is actually possible after all: a close complex border that seems to yield increasing numbers of "close calls" sounds exactly like the situation where there's a lurking, sparse class of "touches" that we haven't thought of, particularly when under 100 years of research has been put into the topic.
- nl 9y agoThat seems like an extremely crap reason to believe a mathematical theorem. What am I missing? What's the alternative? As I see it, the possible ways to think about it are as follows: 1) You must think of it as 50/50 possibility of being true until an absolute proof is found. 2) You look at places where it could fail, and if it passes then you update the likelihood based on that. To me (and as this post argues) it makes sense to follow (2). Not only is it more useful practically (you can use that assumption to solve other things, conditional on it being true) but also it reflects the reality of the world. Even if it turns out not to be true in every case it is clear that in the majority of cases it is true. Maybe it is untrue but it is possible to define the set of cases where it is untrue. If this is the case, it seems likely that class is very small, so it is mostly true. That is the opposite of a proof of course, but it does seem reasonable to think about your confidence of it being true as being somewhat proportional to the likely size of the class. close complex border that seems to yield increasing numbers of "close calls" sounds exactly like the situation where there's a lurking, sparse class of "touches" that we haven't thought of That's not really how it works though. If it keeps happening and those classes don't touch, then it typically means they aren't as close as they seem (ie, there is an extra dimension in which they are a long way apart). In this case it seems like the P/NP divide is actually a thing which means things which appear close actually aren't, so if you analyze them in that space they don't appear close together at all.
- Filligree 9y ago
- Grue3 9y agoOk, but how long did it take to find a polynomial algorithm for primality checking (published in 2002)? [1] And NP-complete problems are even harder than that! The history of mathematics is rife with conjectures that would be considered true if viewed "scientifically", but have an extremely large counterexample that disproves the whole thing. [2] [1] https://en.wikipedia.org/wiki/AKS_primality_test https://en.wikipedia.org/wiki/AKS_primality_test [2] https://en.wikipedia.org/wiki/P%C3%B3lya_conjecture https://en.wikipedia.org/wiki/P%C3%B3lya_conjecture
- CJefferson 9y agoNothing comes close to P=NP. Again and again, across thousands of problems, almost everything ends up being P or NP-hard, and never both. It is certainly possible that P=NP, but it will involve basically starting most of the last 30 years of theoretical computer science again.
- baddox 9y agoI love the “electric fence” examples, but I’m not as skeptical as Scott that perhaps humans simply haven’t invented the mathematical tools required to break this fence. Isn’t that something that has happened plenty of times? You could pretty easily write a parody of this article focused on taking square roots of negative numbers. For generations it looked obvious that no matter which number we tried to square, it would never result in a negative number. You can see the same sort of electric fence that can’t just be a coincidence: we can find the square root of zero, but even the slightest bit less than zero and suddenly there is no square root! Obviously this sounds silly, because we know that mathemticians invented a new tool: imaginary numbers (a name apparently given mockingly by critical mathematicians), which can be used not only to find square roots of negative numbers, but also to solve problems that don’t obviously involve square roots of negative numbers.
- pvg 9y agoIt sounds silly because the analogy is a bit silly. Mathematicians didn't spend centuries trying and failing to take square roots of negative numbers, endlessly studying this as some sort of important question or goal. Complex numbers popped up fairly quickly after the serious study of the roots of polynomials began. They're intrinsic to it. https://en.wikipedia.org/wiki/Complex_number#History https://en.wikipedia.org/wiki/Complex_number#History P≠NP is not like that.
- EGreg 9y agoReminds me of this http://www.lbatalha.com/blog/feynman-on-fermats-last-theorem http://www.lbatalha.com/blog/feynman-on-fermats-last-theorem
- deleted 9y ago[deleted]
- mcguire 9y ago"Telling truth to competence." Brilliant.
- rcthompson 9y agoMore generally, we can show that the attitude that regards any unproven statement as having a 50% probability of being true is trivially self-contradictory. Suppose X is an unknown number, and all we know is that it's between 0 and 100. We can make the following statements about X, none of which is provable with the information we currently have: 1. X < 1 2. 49 < X < 51 3. X > 99 If we assume that each of these statements has a 50% probability of being true, then we trivially get a contradiction, because the probability of the union of these 3 options becomes 150%, because mutually exclusive probabilities are additive. So the idea that a 50% chance of truth represents a state of no knowledge about the truth of a statement is just wrong. If we actually knew that any one of the above statements had a 50% probability of being true, we would clearly have more information about X than we would otherwise. There is no sense in which a 50% probability of truth is a useful default.
- newen 9y agoYou are misapplying probabilities here. If you assume no knowledge, and you have two options for X, true or false, then it's a 50% probability of X being true. Similarly, if there are N possibilities for X, and no prior knowledge for X, then it's 1/N probability of X being on of those possibilities. The key is what prior knowledge you bring to the table.
- rcthompson 9y agoThe random variable X has an infinite number of possible values (real number between 0 and 100). But each of the statements I made has two options: true or false. Despite each having two options, there's no way that all 3 statements can have a 50% probability of truth. The whole point of my comment was that "no prior knowledge" cannot possibly be equivalent to "equal probability of all options".
- skissane 9y ago> The whole point of my comment was that "no prior knowledge" cannot possibly be equivalent to "equal probability of all options". But your scenario isn't "no prior knowledge". In your scenario, you know X is a real number between 0 and 100, which is prior knowledge. And, so the correct thing to do, is use that prior knowledge to assign probabilities, which gives you 1%, 2% and 1% for each of your propositions, not 50%.
- grzm 9y ago(2014)
- justifier 9y agoAre there other theories that rely on the assumption that p≠np? Like how there are theories that begin "assuming the reimann hypothesis|goldbach conjecture is correct.." Disclaimer.. it is my intended inference to show that p=np
- SAI_Peregrinus 9y agoThe existence of one-way functions is one of those things that requires P≠NP. So all cryptographic hash functions would be broken.
- justifier 9y agoI was thinking along the lines of a practical and novel solution to another problem built on top of the assumption p≠np But fair point, that is usually why I say such confidence in those technologies is disconcerting