ABSTRACT
Prologue In a nutshell: the P vs NP question deals with a class of problems whose solutions are easy to test but hard to find. The best known example is the travelling salesman problem: given n cities and k gallons of gas, which is the route, if any, that goes through all n cities and uses at most k gallons of gas? There are many known algorithms that get the solution – alas! – all known algorithms operate in exponential time on the length of the input. However given a possible solution which was whispered to us by some well-meaning guardian angel, it is easy (that is, it is time-polynomial on the length of the input) to test for it – to make sure that the guardian angel wasn’t some mischievous little devil in disguise . . . So, if solutions are easy to test, we may ask, are they also easy to find? Is there a fast, time-polynomial, algorithm that finds a solution for the travelling salesman problem? This is the P = NP problem. Its negation will be noted P < NP: it means, there is no such a fast algorithm.1
