On Resolving the P vs NP Problem

or, on checking claims of resolving famous open problems

Oded Goldreich

In my FAQ page, I stated that I will refuse to check claims regarding the resolution of famous open problems such as P versus NP. I would also advice other experts to do the same, unless the claim is augmented by a clear and convincing indication as to how this work succeeds where many others have failed.

Needless to say, the famous open problems of Computer Science are very appealing, interesting, and natural. As such, they also attract the attention of non-experts, and one annoying consequence is a flood of false claims of resolutions of these problems. These claims are never supported by any new insight nor a clear and convincing argument as to what makes the authors believe that they have succeeded where many others have failed. Having the relatively few expert proofread all these false claims would constitute a vast waste of scarce resources.

It is indeed possible that a non-expert may succeed where experts have failed, but such an event is very unlikely. Furthermore, I believe that in such a case, the successful non-expert will be able to convince the scientific community that his/her claim is indeed valid, and in particular will be able to bypass or break the ``wall of refusal'' erected in the previous paragraph. In particular, it is most likely, that he/she will be able to present a novel insight that would be intriguing enough to convince experts to read the work.

I do not advocate not thinking about the famous open problems, although in my opinion a fruitful approach would be to try to gain more understanding (via easier related problems) rather than trying to make a super-ultra-giant step.

Back to Oded Goldreich's homepage.