5 ms·
Issues in the Proof that P ≠ NP
- sprout 16y agoHead spinning. At least I got that bit about LFP... mostly. The coolest thing about this all is watching the Internet doing what it was built for. Real-time collaboration on a massive scale. The whole of the relevant scientific communities all in one virtual space clamoring at a hundred virtual whiteboards. I love living in the future.
- Jun8 16y agoPrecisely! I found the crowdsourcing approach that got started at http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-cro... amazing. Terence Tao had done a similar thing, not for paper review but to prove some theorems. Compared to this, the rigid approach adopted in Math Overflow to close any discussion on the issue seems so 19th century. See the discussion here: http://meta.mathoverflow.net/discussion/590/ http://meta.mathoverflow.net/discussion/590/
- sidww2 16y agoI think the stance taken by MathOverflow is correct. It would be one thing if that were the only venue to have a discussion about the proof validity possible but there exist much better discussion mediums. The linked blog is a case in point. MathOverflow is geared towards being a Q&A site.
- aswanson 16y agoTotally agree. MO seems to enforce an rigid, sanitary culture for precise question and answering. Perfect approach to mathematical discovery and enlightenment.
- eru 16y agoWhat makes you think so? I always found the process of discovery (when you are working stuff out on your own) to be quite messy. You clean up only after you have found your way. For discovery by reading another one's work, I agree that cleanliness helps. (That's one of the reasons to clean up your work in the first place.)
- aswanson 16y agoThe communication part, which you alluded to in terms of reading someone else's work, is what I was referring to.
- mfukar 16y agoI wouldn't trust a (relatively new, correct?) Q&A site with commenting on research-level work, at least not above the level of informal chat. While outsiders, id est people largely not acquainted with the subject at hand or lacking the expertise, can provide a fresh perspective, I would not expect the benefits from a discussion on such a high-level to outweigh the potential distractions and/or misguided approaches. Let alone other issues that arise with discussing unpublished work. On the other hand, a discussion in the spirit of "what are the concepts behind this proof?", or "what are the implications if this proof is correct/wrong?", or even "what is the approach of this proof? what are the pitfalls associated with such a process?" are excellent ways of disseminating knowledge and educating about the subject a) without having to resort to the few experts on the field and b) keeping the content in line with the principles of a Q&A site.
- omaranto 16y agoYou don't sound familiar with MathOverflow: it is for research level questions in mathematics, and for the most part lives up to that purpose. The reason I wouldn't want to read about this paper there is that the MathOverflow users don't seem to include many computer scientists; they are mostly mathematicians who work in non-computery areas of math. In other words, I would go to MathOverflow for comments on a breakthrough paper in certain areas, just not this one.
- joe_the_user 16y agoI haven't looked at the proof in any kind of detail. But comments by Jame S. Gates etc. raise a question in my mind. Any statical argument that a given phenomena is unlikely is based on the space of phenomena behaving very roughly "communatively" - AB and BA equally likely or at least correlated. How do you apply that kind of reasoning to a totally arbitrary process of computation, a process which wouldn't necessarily have respect any kind of randomness? It seem like any statistical argument for P=/NP has to have a detailed and direct discussion of how you can escape this problem. Anyway, that's my crude effort to translate the discussion into my mere math MA understanding...
- Tichy 16y agoI also don't have high hopes for the statistical angle, in fact I seem to remember that statistical arguments have been around for a long time. But they are not good enough as a proof.
- tetha 16y agoNote, I have not read the paper in detail yet, I just want to explain certain statistical proof techniques which are quite counter-intuitive to me, and maybe help you :) You can, for example, show the probabilities of certain properties of an algorithm and use these probabilities in order to show the possibility of something existing or the absence of something. Furthermore, you can for example use the expected value of a certain process to demonstrate that solutions with a certain value exist. For example, if you are able to demonstrate that the expected value of a maximum cut is 5 for a family of graphs, then you can conclude that there are maximum cuts in this family of graphs which have the value of at least 5. There are some with less, and there are some with more, but cuts with weight more than 5 exist. Or, for example, if you can demonstrate that the probability of a turing machine in a certain class accepting or rejecting after a polynomial time of steps is 0, then it is impossible that this class is identical to P. On the other hand, if it is possible to demonstrate that this probability is not 0 (and thus larger), then we demonstrated that the cut of this class and P is nonempty.
- nonce3232321 16y agoProbabilistic arguments for deterministic systems are standard practice. Search for Erdős and probabilistic methods to see several examples in combinatorics. In computation theory many proofs have the tagline "...with probability 1", meaning the author enumerated all desired possibilities and showed their probabilities summed to one. Most people accept this as proof, although it is less preferred, in the way that proof by contradiction is less favored than direct proof.
- hristov 16y ago"The coolest thing about this all is watching the Internet doing what it was built for." And that would be commenting on a paper before anyone has finished reading it? Just kidding.
- Confusion 16y agoWell, that's an interesting point actually. Not just commenting before they have finished reading it: also commenting without enough knowledge to say anything useful about it. Moderators on meta.mathoverflow.com decided not to allow possibly premature discussions on mathoverflow: http://meta.mathoverflow.net/discussion/590/ http://meta.mathoverflow.net/discussion/590/. The arguments are quite reasonable: So answers could linger on MO asserting that some parts of the proof are correct, other sketchy, other flat out wrong and precious few people will be able to decide for sure if this is true or not.
- sprout 16y agoConsensus is an imperfect metric. Some of those things, even if discarded by consensus in the near-to-long term could prove valid in a couple years' time. We want as many avenues of exploration as possible, even once the proof is decided right or wrong.
- tqft 16y agoA minor point: that decision on meta.mathoverflow.net barely involved the moderators at all. One said what he was inclined to do, but otherwise it was the MO community.
- tetha 16y agoI am not entirely sure about myself here, but I think, I kind of like the way people handle this. Sure, there will be a lot of questions which are trivial to someone deep in the field and even more questions which are already answered in the paper, but these should be removed pretty fast. However, those questions which are not answered via "See page X" or "Look in that book, page X" will need explanation and will strengthen trust in this proof, should it be correct.
- amichail 16y agoCould it be that the million dollar millennium prizes are actually slowing down the resolution of important problems because they discourage crowd sourcing proofs?
- deleted 16y ago[deleted]
- fizx 16y agoIt seems possible to me, but doubtful. Even contributing work worth a footnote in the wikipedia article about solving P =? NP would validate a lifetime of research to many people.
- pgbovine 16y agowell, you can't crowdsource everything ... sure, crowdsourcing things that most humans can do (e.g., labeling images) works pretty well, but solving open problems in math or composing masterful works of literature, eh more doubtful. the crowds are only wise in certain respects.
- philh 16y agoMathematics has been crowdsourced effectively. See: http://www.thebigquestions.com/2010/04/08/blogging-tic-tac-toe-and-the-future-of-math/ http://www.thebigquestions.com/2010/04/08/blogging-tic-tac-t...
- Groxx 16y ago>... because they discourage crowd sourcing proofs? Do they? It seems it would be valuable in any pursuit, as it costs the reviewers less. It certainly discourages crowdsourcing solutions, as then how do you split the winnings, but proofs? That seems to require an attempted solution first, to be checked, in which case credit is pretty easily assigned.
- j-g-faustus 16y agoI may be out of tune with many others here, but I think certain constructive processes (as in creating a many-faceted proof, outlining overarching software architecture, making the storyline of a good novel/movie) are most efficient with small groups of people. Otherwise you run into issues of "design by committee" or "too many cooks". It is easier to crowdsource once the main outline is in place, it structures a vague problem into a set of more specific subtasks that can (more or less) easily be distributed across many people. Like in this case: Deconstructing an existing proof can work very well with crowdsourcing, since a proof contains a relatively small set of specific claims, and each "crowd" contributor can focus on one particular issue. But this works because the crowd now has a common focus point and task list created by the paper being published. It's not clear to me how (or whether) the process could be reversed, that the same crowd and effort could be coordinated to cowrite an original paper with an alternative proof.
- Sephr 16y agoLearn to use the DOM instead of HTML strings, and you'll almost never run into those XSS problems. You can replace all of your HTML sanitization functions with document.createTextNode(text).
- Figs 16y agoI think you're looking for a different thread...
- paraschopra 16y agoNo, given how cryptic the original post looked to me, the comment looks absolutely spot on!
- Sephr 16y agoOops, I meant to reply in the thread about that node.js chat application full of XSS holes.
- cdavidcash 16y agoIt seems like a bit much to hope to understand and verify the proof without a huge investment of time and effort. The problem is exponentially compounded if you don't already do research in theoretical computer science and have the appropriate logic background. But! All of this has put a spotlight on a theorem that I had somehow never appreciated. It is a beautiful theorem that is well within reach of a mathematically-literate computer scientist: P = FO(LFP) over finite ordered structures. If you start reading up on this, it's immediately clear that this is interesting, because FO(LFP) say nothing a priori about computational resources in the sense that P does. Anyway, a sufficiently curious reader can look it up as theorem 4.10 in the following text: http://www.amazon.com/Descriptive-Complexity-Texts-Computer-Science/dp/0387986006 http://www.amazon.com/Descriptive-Complexity-Texts-Computer-... That book is pretty light on the basics of logic. I used this book: http://www.amazon.com/Mathematical-Logic-Undergraduate-Texts-Mathematics/dp/0387942580 http://www.amazon.com/Mathematical-Logic-Undergraduate-Texts...