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 a^{d}=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.