# Why it is hard to prove that P does not equal NP.

The most famous problem in theoretical computer science is the question of whether P equals NP. An astonishing paper of Razborov and Rudich gives a very clear reason for the difficulty of this problem. They define a notion of a `natural proof' that P does not equal NP, show that all known methods for proving related results are natural in their sense (which is indeed natural) and then show the following conditional result: if there is a natural proof that P does not equal NP then the discrete logarithm problem (given a, x and a prime p, find d such that ad=x mod p) is solvable in a relatively short amount of computer time (which implies, amongst other things, that it is not too hard to factorize large integers). Since it is widely believed that there is no quick algorithm for the discrete logarithm problem, it looks very unlikely that there is a natural proof that P does not equal NP. On the other hand, it is hard to imagine what an `unnatural' proof could possibly be like.