Until a major chorus of experts chimes in with "Yup, this is curtains for this approach", I think it would be wise not to take too seriously any blog comments based on quick reactions to the paper.
...just as it would be unwise to take the paper itself too seriously until a chorus of experts tells us that it's looking pretty good.
Tao has little expertise in the area, and he isn't pretending to -- he's deferring to those who are more knowledgeable. He happens to frequent these particular blogs, but he isn't making any statements as to the correctness of the proof.
However, the linked comment is the first major statement from a well-cited researcher (aside from S Aaronson, who hasn't even read the paper yet)
One expert finds the flaw, calls it "unfixable" twice, and another seems to agree. This is good enough for social news -- which while not always reliable is often ahead of the mainstream press.
removing the paper doesn't necessarily mean that at all, he probably just wants finish editing it and getting peer feedback before he releases it officially
well he had actually posted an updated version yesterday, so if he had to update it he would put up a not. Regarding the legal question, i don't think it reflect poorly any way on HP Labs. Its not like he is making cranky claims like no one landed on moon etc. etc.
I thought his paper was showing P/=NP which is the already (more generally) accepted theory in computer fields. I'd understand it reflecting poorly if one of HP's researchers was claiming P=NP against the accepted wisdom. It would however reflect great if this guys paper is a proof of P/=NP or even if it's simply a step forward.
It would be extremely unwise of HP to shut him down - regardless of whether his proof works out in the end, this is a significant piece of work contributed for the further understanding of hard math problems - which is what HP ideally wants to represent. To say no to endeavours like this would be to say that they have no soul and no will for the enhancement of human knowledge.
He just posted a new version of the draft, and added this blurb to his home page:
"Vinay Deolalikar. P is not equal to NP. 6th August, 2010 (66 pages 10pt, 102 pages 12pt). Manuscript sent on 6th August to several leading researchers in various areas. You can find the current version here. Please note that the final version of the paper is under preparation and will be submitted to journal review."
So it seems this is the defender our star forward has to get past to hit the ultimate math-world goal. We can now root for our respective teams... Go defenders!
I'm rooting for defenders on the principle that the present proof doesn't seem illuminating. I'd prefer a proof that seemed to give insight into the nature of complexity itself. But it's still just a diversion...
If I can understand the complexity classes themselves as well as the consequences of P = or != NP (which I believe I can), then it seems like I should expect (or at least hope for) a similarly-comprehensible proof.
Contrast that with, say, special relativity. I can't even really understand the consequences of special relativity (length contraction, relativity of simultaneity, time dilation, etc.) beyond accepting that my intuitions are completely errant at relativistic speeds. Because of that, I don't really expect or hope for an intuitive proof or explanation of special relativity.
Granted. I do think problems in the domain of number theory are a bit different. I don't know of any quickly-explainable consequences to Fermat's Last Theorem, and in my first comment I was really thinking about consequences. With Fermat's Last Theorem, to my knowledge, the original problem is itself pretty arbitrary, so I'm not surprised to find its solution and proof to be complicated despite the simplicity of the problem statement.
Also, I'll preemptively mention that Gödel showed us that any formal problem is a problem in number theory. That said, a problem like P =? NP would almost surely be incomprehensible if expressed as an isomorphic problem in number theory. So my original point, clarified and rephrased, is that I would expect (or desire) the proof of a problem to be as intuitive as the statement of the problem combined with its consequences in the domain the problem is stated.
I don't know the history of mathematical theories, but in physics it has often been the case that something took years (or decades) for people to wrap their heads around as they were poking at the edges of understanding. But as they continued to do so, new ideas and concepts emerged which made a better mental framework for understanding them. Hence, for example, the work-energy theorem can now be proved by a high school senior, but in the day there was big debate over the factor of 1/2 in the term for kinetic energy.
So it may be with mathematics. Things like Fermat's Last Theorem and P != NP may be difficult to grasp simply within our current frameworks, but new ideas may give rise to new frameworks that makes them more digestible.
If you can just get it proved somehow then you can proceed with confidence towards these new ideas.
indeed. there are probably not many people on HN or people who are going to post comments on blogs that are qualified to actually weigh in on this type of thing.
It is a bit sad though for the author. The author never intended the paper to be public. Now he joins the infamous list of people who published to prove P!=NP or otherwise.
It is sad for the author, but not because he will join that list - he is not. He is going to join the much less famous list of people who attempted to prove a very difficult problem, did so in a professional way, and while they ultimately failed they did advance science.
And whomever leaked that is going to end up on the shitlist of an entire community of researchers.
If someone seriously wants to only share their P!=NP proof privately, they need to put "not for wide circulation" as a watermark on every page.
But who know what the authors thinking was? Perhaps he hoped they'd share the paper only if they were sure it was right, perhaps he expected they wouldn't share it at all. Perhaps he expected they'd share it and he was already convinced the paper was correct. Perhaps he didn't care to what people outside the field thought...
If I get a paper with request for comments in a personal mail from an author, I would definitely ask permission before forwarding. Not doing so is just rude.
It's so strange to realize how incredibly massive the field of mathematics is.
As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. (Edit: of course, now I regret writing this. What I meant was: I can read, understand, and re-implement 99% of software engineering algorithms / architectures.)
But to know that it would take someone as insanely experienced as cpervica years of study to understand that proof... Wow.
He mentioned he's a "developer", and from his point of view, (and mine), the field of practical programming knowledge is pretty limited. So he could roll up to a Barnes and Noble, pick up most any book and learn the concepts in it no problem.
But on the other hand, couldn't P=NP be considered "programming concept" itself? But on the third hand, maybe
once its figured out, it will be a concept he could learn in a day.
At this point, I have >10 years of programming experience. I've been programming for the majority of my childhood and the entirety of my adult life. I don't like to overestimate my own abilities, and I wish I could prove to you that my above claim is true. I simply have enough experience where I know for a fact that I can understand 99% of algorithms and architectures that were designed to solve a practical real-world problem.
So you're right, "there isn't a single..." is probably pushing it. But I'd definitely stand by the fact that I can read, understand, and re-implement 99% of algorithms or architectures.
My point is simply that the breadth of the field of software engineering apparently pales in comparison to that of mathematics.
Or rather --- it's very strange to me that if you are an expert in a given branch of mathematics, then all of your lifetime of experiences cannot be applied to an entirely different branch. If I understand cperciva correctly, if you want to learn a particular specialized branch of mathematics, then you basically have to start from the ground-up (years).
It would basically be equivalent to wiping your memory of all programming knowledge, then re-learning it all, in terms of effort. It's just strange / interesting that mathematics works that way.
You are basically saying you could re-write the H.254 codec just by studying it for one day? Sure you might be able to learn some of the image compression tricks that it uses by reading the spec but to implement it efficiently requires deep understanding of hardware architecture, instruction pipelines, bit-twiddling algorithms and dare I say it, mathematics.
You are right that mathematics is unique in being an infinitely broad subject. Programming as a subject is like medicine in that it is constrained by the real world. However, I don't know about you but I'm not going to trust a radiologist to perform surgery because he's 'understood' the concepts in one day.
I remember being shocked when I found out that my wife, in advanced undergrad courses, was routinely expected to pick up current biology and biochemistry research papers and be able to read them.
Conversely she was shocked to realize that people in mathematics couldn't. And that you could easily complete a masters in mathematics without once being asked to try to read a real research paper.
Conversely she was shocked to realize that people in mathematics couldn't. And that you could easily complete a masters in mathematics without once being asked to try to read a real research paper.
That shocks me, too. I'd expect anyone completing a master's degree in mathematics to have published at least one paper, never mind reading others' papers.
Read, yes; publish, no. I did my undergrad in math and am friends with many math master's/PhD students at UBC. I can't imagine getting a master's without reading a research paper. If that happens somewhere, I wouldn't think that their degrees are worth very much.
Publishing is another story. Reading current research is one thing... actually successfully advancing the state of the art in an area of pure math is quite another. (Applied math is another story altogether).
> I can't imagine getting a master's without reading a research paper. If that happens somewhere, I wouldn't think that their degrees are worth very much.
The University of Chicago awards ‘incidental’ master's degrees at the end of the first year of graduate study (http://catalogs.uchicago.edu/divisions/math.html). Although it's certainly possible to be reading current research at that point, I wasn't; and yet I think it's fair to say that U of C degrees are worth something.
I know a number of people who completed master's degrees in pure math who I suspect had not yet read a paper, and who definitely had not published one.
Personally I published my first paper in undergrad. But that was considered unusual among the people I knew.
Skimming over the paper, the goal appears to be "convert an arbitrary closed concave polygon into a set of triangles in linear time".
Disregarding the "linear time" part, there is a standard way to accomplish this goal:
- the polygon can be thought of as the "outline".
- transform the outline into a set of XYZ positions (verts). This is accomplished simply by starting at any point on the outline, then stepping along the outline by a fixed interval until you wind up back at your start pos.
- then:
triangles = []
while len( verts ) >= 3:
for i from 0 to len( verts ) - 2:
A = verts[i]
B = verts[i+1]
C = verts[i+2]
# verify the triangle has not been flipped inside-out, and is not degenerate.
det = Determinant2x2( A - B, C - B )
# if the triangle is degenerate, then remove the middle vertex.
if det == 0:
verts.remove( B )
break;
# if the triangle is inside-out, skip it.
if det < 0:
continue;
# if the triangle does not intersect the polygon and is not inside-out, then it is a valid triangle, so add it to the result.
if not TriangleIntersectsPolygon( poly, A, B, C ):
triangles.append( [A, B, C] )
verts.remove( B )
break;
This is known as 'ear clipping'.
Now, it is not linear time, but there is no reason to optimize this algorithm unless it turns out to be necessary, which I've never yet seen to be the case in an actual real-world scenario.
That's the thing about scientific papers --- they are very useful, but only if your problem domain precisely matches theirs. For example if you don't care about "linear time", then all of that paper's complexity simply fades away.
This is like someone challenging me to implement merge-sort, and then I give him the solution to bubble-sort saying that there's "no reason to optimize" until necessary.
Granted the cases where Chazelle's linear time algorithm is necessary is less than merge-sort. But that is true of any field, including mathematics.
Yes, yes. But the original challenge is invalid. I asserted that I could implement 99% of algorithms I came across for practical real-world problems, not 99% of all algorithms.
I gave a solution that solves the problem. The problem is, convert an arbitrary concave closed polygon into a set of triangles. I maintain that it is completely valid for me to present that solution --- there are plenty of tricks you can do to optimize it in C/C++. And not just runtime optimization either... For example why not triangulate the polygon, then save the results to disk? That way O(N log N) vs O(N) becomes completely irrelevant... you only have to do it once, ever.
I suppose what I am saying is this: I can solve 99% of real-world problems I am likely to encounter in my career as a software engineer. The challenge "implement THIS scientific paper!" is completely invalid because it's a solution to a problem which very likely will never exist. My solution is valid as long as it does not greatly impact the performance of the app. Which is "always", once you throw in a layer of caching.
P.S. The paper has the restriction "for every polygon vertex XY, no two vertices may have the same Y coordinate", which means it's likely to not be applicable to any real-world problem.
Why is it invalid? Your original comment made no mention of "practical real-world problems". Who gets to decide that? Is implementing a video codec not a "real-world" problem since only a handful of people have experience with this? What about symbolic algebra software? A handful of find those useful compared to the masses that require mundane enterprise crud.
Memoization is not panacea. This is like telling someone to sort every possible group of numbers and saving it to disk so you don't have to implement something faster than bubble-sort.
My point is that in any field, "99% of real-world problems" are easy enough for the average college graduate to comprehend. Think about the kind of math that is useful for "real-world" problems. When you start bragging that you can learn any CS topic/algorithm in less than a day, you just didn't look hard enough.
P.S. You missed the sentence right after where it says "we can easily get around this assumption by applying the symbolic perturbation techniques of [10] and [31]"
It's invalid because the paper was presented to solve a problem which does not exist. Maybe it can be applied to some other problem using similar theory, but the problem it presents would basically never have to be solved in linear time. Try to think of an application where realtime triangulation of dynamic (changes every frame, negates the possibility of caching) concave polygons is an such a bottleneck that it not only requires hand-optimizing your triangulation routine, but also requires you re-architect it to run in linear time. In Google's words, it is a "solution in search of a problem".
Memoization is not panacea. This is like telling someone to sort every possible group of numbers and saving it to disk so you don't have to implement something faster than bubble-sort.
I really am not trying to be mean, I'm just stating the facts -- your statement is so full of ignorance that it's kind of disturbing that you believe it. Programming is generally an exercise in caching. There was a good article posted a long time ago called It's caches, all the way down. If you think about it, memoization (a.k.a. 'caching') has been the primary solution to a large percentage of past problems. The examples off the top of my head:
- GPU memory is a cache of system memory
- system memory is a cache of the hard drive
- the operating system presents a file I/O interface which heavily utilizes caching
- John Carmack developed Quake which revolutionized the realtime graphics industry primarily because of his innovative "potential visibility set" algorithm, which is just a cache of computing visibility on-the-fly
So for all intents and purposes, memoization (caching) IS the magical panacea that you deny it to be.
How do you know the problem doesn't exist? Even if you are pre-computing it, wouldn't you like it to go faster, like encoding a video or rendering a ray-traced scene? There are an infinite number of polygons.
Of course caches are important. But it isn't the only thing. That's why programs aren't all giant databases. Memoization != better caching either. That is simply naive. If your algorithm can fit in L1-L2 cache, it can be better than loading a giant hash table or tree from disk.
I'm not trying to be mean either, but you have all the signs of a junior developer who thinks there is nothing left in CS to challenge him as he churns out enterprise crud where caching is the only thing he can think of that matters.
Because the problem applies primarily to realtime 3D / 2D graphics, of which I have spent the last 7 years learning about. That is of course not a guarantee the problem does not exist, but it is very likely. Otherwise, it would be one of the significant known problems in realtime graphics.
Even if you are pre-computing it, wouldn't you like it to go faster, like encoding a video or rendering a ray-traced scene?
What I want is irrelevant. All that matters is what the application needs to do. It is a senseless waste of time to optimize a sufficiently fast algorithm.
There are an infinite number of polygons.
There are an infinite number of numbers. This has no bearing on the problem, on the effectiveness of caching, or on any other of my points. In other words, this is yet another completely irrelevant statement by you.
You have all the signs of a junior developer who thinks there is nothing left in CS to challenge him as he churns out enterprise crud where caching is the only thing he can think of that matters.
Oh, really? I did you the courtesy of explaining exactly why your earlier statement was so full of ignorance. You merely insult without reason or basis. Congrats, you are a troll and have been trolling this entire time. This means you have not only completely discredited yourself, but are also no longer worth trying to disprove, because your statements are without reason or merit. Which is quite sad, since I personally was interested in an opposing viewpoint; but not if it's completely insane.
Have you even solved any problems related to "polygons" in your programming career? Also, how long exactly have you been programming for? I have been programming for ten years. I'm trying to find one good reason to take any of your statements seriously. Unless you have any graphics experience, or more experience in general, I see no reason to. And since you have neither logic nor tact, I see no reason to continue this conversation.
I just explained to you the reasons why you are wrong which you have conveniently disregarded.
Instead of rising up to the challenge or admitting failure, you make broad sweeping generalizations like you could learn 99% of any CS concept in less than a day, and that any challenge that you are not willing to do (or likely cannot), is because the challenge has no "real-life" application.
Not only did you read the paper incorrectly, trying desperately to find holes in it, but you try to change the subject by calling me naive in my refusal to allow you to just say "memoize" as the answer to any algorithmic challenge. I think it is clear to anyone else reading this that you are in the wrong here.
I already explained exactly why the algorithm has no real world application. The burden of proof is now on you. And until you do, I maintain the challenge was completely invalid.
"What I meant was: I can read, understand, and re-implement 99% of software engineering algorithms / architectures."
While this may be true, you are comparing apples to oranges. "Read, understand and re-implement software algorithms / architectures" is to computer science as "Read, understand and apply some given formulas to solve a problem instance" is to maths/physics.
Formalizing and proving the correctness and boundaries of these formulas is the hard part here, where mathematicians are doing their job. You probably can implement a Support Vector Machine in one day given a detailed pseudo-algorithm, but truly understanding the underliying concept, as well as its weaknesses and strong points is way harder. Let alone improving it. And the very same thing can be said about a lot of other algorithms (MRF-optimization, coding theories, etc.).
Was it ever there? I thought he always said that the paper was done on his personal time and not related to his HP research. I read his Bio there Sunday/Monday and dont remember seeing it. Not to mention it was still being peer-reviewed when it was leaked.
He posted something saying that it wasn't meant to be released yet. He had sent it to some experts on August 6th and it made its way into the wild on August 8th. He posted what he said was an "updated" draft. It was there this morning but is no longer.
Yes but you've linked to a comment to the main blog post. Which is a bit untoward. A comment on a blog is hardly authoritative. I did a double-take until I realized you weren't linking to the main post. The main blog post says (and I quote) Still there remains the key question: is the proof correct? In one sense the present paper almost surely has mistakes—not just from the above objections but what one could expect of any first-draft in a breakthrough situation. The real questions are, is the proof strategy correct, and are the perceived gaps fixable?
edit: the commenter Charanjit Jutla seems to know his stuff but I still maintain that an offhand comment does not warrant the definitive titling of your submission.
Do a quick search on the blogs and the names of people posting comments on it. They are authoritative sources, just because it is on a blog (run by a well known complexity theorist) doesn't mean it's less important. I am quite surprised to see so many comments from these guys and such a discussion happen in public.
They don't necessarily agree with each other, though, so I'm not so sure how "authoritative" individual blog comments are (see e.g. Bradfield's followup to Jutla -- "And I don’t understand your comment about it not being known whether mu-calculus has a hierarchy of expressibility in alternation. It’s 15 years since I (and independently Lenzi) proved that it did!")
All these academics that lay low then pop up with problems and call Deolalikar's contribution unfixable infuriate me.
They bring out the worst in the same way that bad QA employees do. They create no wealth and add little value. They slow down and confuse the process. But in the end they are still necessary. There is something to be said about how one reports such problems. Most here know a great QA person that reports relevant problems in a intelligent manner and is there to help find solutions. Versus the QA person that just cranks out an endless stream of wonky insane problems. All make you look bad and all are difficult to reproduce, understand or address.
It's my understanding that his approach is a radical and new way to attempt to solve the P!=NP problem. So it's no surprise that at first glance the vast majority of average math and computer scientists would think it was not a valid approach. And, again no surprise to me, that has ended up to be the case. I don't pretend to understand this flaw or Deolalikar's paper. But I do understand the type of person that posts comments like that...
It looks like the math community has settle on a wiki to unofficially collect news and information on the paper:
The claim is that the proof is unfixable. Proofs are either right or wrong. Good academics are supposed to checks proofs of their colleagues. There is no claim as to the merit of contributions made by Deolalikar. So, why exactly do these academics infuriate you?
I'm quite clear if you read more than one sentence.
It's the way this guy responded to a comment of a blog about the paper. It just seems like a bad place to post a real unfixable flaw to the paper. Assuming the commenter is right (also possibly a bad assumption) why not put some effort into your response that will be read by every computer science and math person you'll ever work with in the future. For instance how does one respond, follow up, contact this guy? I have to go google him wtf. It's the equivalent to nitpicking. In the end someone else will have to pick up the pieces of what he said and analyze it and rewrite it and repost it. So to me he seems like the guy from QA that no one wants to work with - a bad team player.
Most people's work, when submitted, gets reviewed by four people, and if published, read by a few people their sub-area of their area.
All of Computer Science is paying attention to this paper, and it wasn't even published anywhere. People popping up out of nowhere is a good thing. It's even a compliment to the work.
Nobody is saying it's a worthless approach. On the contrary-- the reason there's so much hubbub over the paper is that the approach is quite novel. Even if the end result turns out utterly wrong, much of the lead-up in getting there can be salvaged and used for entirely new directions in TCS.
In TCS, new strategies/approaches/techniques are often just as valuable as the results (and in top conferences, they are sometimes considered even more important).
We need to subject every paper to serious criticism in order to establish which morsels have merit. Hand-waving and weak logic seriously impediment our progress, so many researchers get very frustrated by it.
> The only thing that you can say is that this approach was one of the trickier ones to do it in a wrong way.
Or, rather, that someone (well qualified) thinks it was. I am very sceptical of a refutation based on the assumption that the proof founders on a beginner's mistake; it's not impossible, but, if Deolalikar is a beginner in the relevant field (I have no idea!), then it seems very likely that he would have consulted with someone who wasn't to avoid such trip-ups.
> Yet it does not "necessarily" means that this approach is actually a starting point.
I am a mathematician, not a computer scientist; but I think it's safe to say that any approach to a well known problem that is not (1) immediately dismissible (by experts) as crackpottery or (2) a laborious advance an inch down a familiar road of reasoning is likely to represent a promising starting point for something (future research in general, if not the answer to the specific question). If it is (3) described by experts as a novel and/or unexpected approach, as I think that this paper was, then that likelihood becomes a near-certainty.
...just as it would be unwise to take the paper itself too seriously until a chorus of experts tells us that it's looking pretty good.