The Mathematics of P vs NP by hemant pandey - HTML preview

PLEASE NOTE: This is an HTML preview only and some elements such as links or page numbers may be incorrect.
Download the book in PDF, ePub, Kindle for a complete version.

-A DEEPER INSIGHT

image015.jpg

Let  us  now  examine  few  actual  solutions  and  see  whether  they  meet  our  methods  and criteria which we have specified .We would take one of the famous tours namely the optimal tour through 24,978 cities in Sweden [Link to it is provided at the end under the section of references, links and further reading]. Apart from the symmetry we can at once point out that it has two basic properties. To start with we can at once point out that the map has an outer mesh which is a convex polygon or a distorted convex polygon .Further the inner networks seems to be formed of  a lot of independent networks. But the most important point is that we can prove with the help of this network efficiency and working of our method. We can easily point out that our two properties of shortest route are satisfied here. Each of the point is joined to the nearest branch and also each segment is joined to the nearest segment. We also see that no  other  property  than  these  are  either  applicable  or  required  to  this  network  to  be  the shortest route. We can also prove that our method of finding the shortest route is polynomial. Suppose we distort this network and reach at a point in which m points are not joined to their nearest branches, m<n obviously. Now from here we start checking for each point. In less than C(n,2) tests we can find the nearest branch to the point and by joining other points to their second nearest ones we can find whether this change is acceptable or not. So in one step we can find the nearest branch for that point. So after each step one point gets eliminated, and in no more than m steps we get a route which is the shortest with respect to the points. The order of this calculation is n.C(n,2) i.e. 3.The same result is for segment to segment connections. The point to notice is that after each step we discard around C(n,2)  routes barring just one. So in total n’ steps we discard about [C(n,2)]n ways. Since many routes are common this number well exceeds the total number of routes. The point to note is that since we are discarding the routes in steps we need only n’ steps but total number of discarded routes is much more as