Issues in the Proof that P ≠ NP

http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np

by bumbledraven • 16 years ago

108 33 16 years ago

rjlipton.wordpress.com

sprout2• 16 years ago

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.

Jun8• 16 years ago

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/

sidww2• 16 years ago

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.

mfukar• 16 years ago

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.

joe_the_user2• 16 years ago

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...

Tichy• 16 years ago

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.

tetha2• 16 years ago

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.

nonce3232321• 16 years ago

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.

hristov• 16 years 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.

Confusion2• 16 years ago

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.

tetha2• 16 years ago

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.

amichail• 16 years ago

Could it be that the million dollar millennium prizes are actually slowing down the resolution of important problems because they discourage crowd sourcing proofs?

fizx• 16 years ago

It 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• 16 years ago

well, 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• 16 years ago

Mathematics has been crowdsourced effectively. See: http://www.thebigquestions.com/2010/04/08/blogging-tic-tac-t...

Groxx• 16 years 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-faustus2• 16 years ago

I 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.

joe_the_user2• 16 years ago

I'd agree that crowd sourcing might not always be the best way to approach things. But the general situation that the person who gets the final result wins very likely does inhibit effective work on the solution of very difficult problems.

I mean, I think there's a consensus that if Wiles had been publishing his results as he went along, Fermat would have been solved earlier but probably not by Wiles himself. Whether the current N/NP proof is right or not, it also is clearly the product of long work in a vacuum. That's not the best way to do things if nothing else as a matter of sanity. If you're publishing as you go along, you've got a lot more of a sanity check. Further, if research is open, you can do single person, small-committee and crowd-sourced versions.

Still, I don't think this primarily a matter of the Millennium Prizes in particular but of the tremendous competition of academia in general - Wiles' effort happened before the Millennium Prizes - and he couldn't get Fields Medal either - too old.

Oddly enough, the Netflix prize actually seems to have produced a fusion of efforts in the end. Perhaps future prize creators could think about that. Both the Millennium Prize and the Fields Medal seem deeply problematic in their effect on mathematics in general.

Confusion2• 16 years ago

I don't think anyone working on these kind of problems for years is aiming for the M$. That just icing on the cake. The main reason for not publishing partial results (which could be considered to be a sort of crowdsourcing, as it will lead to dozens of people reading and inspecting the results), is that someone could recognize the trail and beat you to its endpoint.

Sephr2• 16 years ago

Learn 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• 16 years ago

I think you're looking for a different thread...

paraschopra• 16 years ago

No, given how cryptic the original post looked to me, the comment looks absolutely spot on!

Sephr2• 16 years ago

Oops, I meant to reply in the thread about that node.js chat application full of XSS holes.

cdavidcash• 16 years ago

It 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-...

That book is pretty light on the basics of logic. I used this book:

http://www.amazon.com/Mathematical-Logic-Undergraduate-Texts...

Issues in the Proof that P ≠ NP

Related Stories