What If NP=P?

Now consider the idea that NP=P and there is a way to solve the problem, as well as test the solution, in polynomial time. This can only mean that there is a way to find a solution which does not require the search of the entire problem space. In the case of the travelling salesman problem, this means that you should be able to tell whether or not there is a tour with a length less than D without searching the entire space. 

What sort of amazing feature could this be?

There has to be some sort of easy-to-compute property, either of the entire network or of the connections, that allow a shortest path or shorter path to be found. For example, suppose every network in the universe glowed with a particular color according to the shortest tour. Now if you want to know if there is a tour less than D in length for a particular network, no matter how big it is, is to look to see how much it glows. Of course, this means you have to have a calibrated scale, but this shouldn't be a problem in P as it requires no searching. 

It this idea of "glowing" networks seems silly, OK it is, but it gives you the idea that the network has to have some physical property that lets you solve the problem without search. In practice, we are looking for a mathematical property that works like a "glow". For example, if I could prove a theorem given a network of N cities that always has a minimum tour of length f(N), where f is a function we can evaluate in polynomial time, then if you need to know if there is a tour less than D for a network with N cities you simply compute f(N) and compare it to D. Problem solved in P. 

Of course, there is no such function of N that works like this - if there was we would have found it a long time ago. There is also probably an easy proof that such a function cannot exist. It certainly cannot exist if P!=NP. However, there might well be functions of other easy-to-compute quantities beyond the number of nodes - number of connections, number of connections less than a given length, and so on. 

Armed with such a global feature as f(N), means you don't have to perform a complete search for the solution. An alternative to this is a feature that enables you to reduce the size of the search - a guiding feature. This is similar to the idea of a heuristic, which is a rule that lets to select options that are likely, but not guaranteed, to give you a good solution. A heuristic could be something like "always take the shortest route to the next city". Such heuristics are used in practice to get reasonable solutions to NP problems. It is the reason that sat navs can provide you with a shortest route. They don't solve the routing problem by exhaustive search they use heuristics to find a solution that is, if not the best, guaranteed to be almost as good.

A heuristic that doesn't just give you a guarantee but gives you the real solution isn't a heuristic - it is an algorithm that solves the problem. If the algorithm runs in P for the travelling salesman problem then P=NP.

Notice that if you have such an algorithm you can use it to find the solution in polynomial time. This means that you could use it to label every network according to its smallest route in polynomial time and so we have a function f(n) where n is the network which gives us the smallest route and so f(n) is a property of the network that solves the problem. 

What all this means is that, no matter how it comes about, there is a function or a property of the network that can be computed in polynomial time that gives the answer to the decision problem by solving the associated NP hard problem.

Testing Primes

This is all a bit abstract and you might think that such properties don't exist, but let's remember the story of prime testing. To discover if a number is prime you simply have to try dividing it by smaller primes - if it divides exactly then it isn't a prime, but if you try all of the possible factors and it doesn't divide exactly then its a prime. Testing for primality in this naive way is exponential in the number of digits in the number you are testing. Thus it isn't in P, but it isn't in NP either as there is no suitable test value that you can use a a shortcut when proving a number prime - you cannot avoid trying all possible divisors. There is no obvious witness for primality.

The complement of testing primality, testing compositness, however, is in NP. You can prove a number is composite simply by giving one of its factors. Testing primality is said to be in Co-NP. 

This seemed to be an obvious fact and was the status quo until, in 1975, it was discovered that there was indeed a witness that you could use to test primality - and hence primality is also in NP. If you have a number p and want to test if it is prime then someone can give you another number such that you can do a simple computation i.e. one in P, that will prove that p is or is not prime. This places testing primality in NP, because given a you can verify that p is prime but finding such an a is not in P. 

So testing primality appears to be in NP, but now we come to the important part of the story. At this stage it really does look as if primality testing is in NP, and soon there were really good heuristics that solved the problem most of the time. For example, the Miller-Rabin test is generally called a strong probable prime test as it finds certificates for primality such that by repeating the test you can reduce the probability that you have made a mistake to as small a value as you like. If you run the test k times then the probability that you will claim p is prime when it is not is no more than 4^-k.

The existence of such effective heuristics suggests that perhaps testing primality is actually in P and the only reason we think it is in NP is that we haven't found the polynomial time algorithm that places it in P. 

Then in 2002 Agrawal, Kayal and Saxena invented the AKS primality test that runs in O((log n)¹²) which places it in P. This takes the form of a function AKS(p) which returns true if p is a prime and false otherwise. It does this without searching for the factors of p. Notice that in this sense AKS(p) is a property of the number p and not something determined by the search. It is this property that makes the search unnecessary. It is as if every number had a color, black or white, with all the primes showing as white.