News for hackers. Stuff that matters.
Re:Issues in the Proof that P ≠ NP by sprout on Monday August 09, 2010 @10:37PM (#1590252)
Head 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.

Re:Issues in the Proof that P ≠ NP by hristov on Tuesday August 10, 2010 @02:48AM (#1590694)
"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.

Re:Issues in the Proof that P ≠ NP by Confusion on Tuesday August 10, 2010 @04:03AM (#1590817)
Well, 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/. 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.
Re:Issues in the Proof that P ≠ NP by sprout on Tuesday August 10, 2010 @11:37AM (#1591818)
Consensus 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.

Re:Issues in the Proof that P ≠ NP by tqft on Wednesday August 11, 2010 @12:04AM (#1593784)
A 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.
Re:Issues in the Proof that P ≠ NP by tetha on Tuesday August 10, 2010 @08:19AM (#1591234)
I 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.
Re:Issues in the Proof that P ≠ NP by joe_the_user on Tuesday August 10, 2010 @12:57AM (#1590501)
I 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...

Re:Issues in the Proof that P ≠ NP by nonce3232321 on Tuesday August 10, 2010 @10:54AM (#1591617)
Probabilistic 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.

Re:Issues in the Proof that P ≠ NP by tetha on Tuesday August 10, 2010 @08:28AM (#1591242)
Note, 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.

Re:Issues in the Proof that P ≠ NP by Tichy on Tuesday August 10, 2010 @06:34AM (#1591063)
I 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.
Re:Issues in the Proof that P ≠ NP by Jun8 on Monday August 09, 2010 @10:42PM (#1590259)
Precisely! I found the crowdsourcing approach that got started at 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/

Re:Issues in the Proof that P ≠ NP by sidww2 on Monday August 09, 2010 @10:48PM (#1590273)
I 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.
Re:Issues in the Proof that P ≠ NP by aswanson on Monday August 09, 2010 @11:31PM (#1590351)
Totally agree. MO seems to enforce an rigid, sanitary culture for precise question and answering. Perfect approach to mathematical discovery and enlightenment.
Re:Issues in the Proof that P ≠ NP by eru on Tuesday August 10, 2010 @07:11AM (#1591122)
What 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.)

Re:Issues in the Proof that P ≠ NP by aswanson on Tuesday August 10, 2010 @10:53PM (#1593664)
The communication part, which you alluded to in terms of reading someone else's work, is what I was referring to.
Re:Issues in the Proof that P ≠ NP by mfukar on Tuesday August 10, 2010 @03:23AM (#1590754)
I 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.

Re:Issues in the Proof that P ≠ NP by omaranto on Tuesday August 10, 2010 @08:03AM (#1591203)
You 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.