1. Introduction

This paper, taking Travelling Salesman Problem as our object, wishes to develop a constructive algorithm to prove P=NP, which is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, and is also a major unsolved problem in computer science. NP represents the class of questions for which there is no known way to find an answer quickly, but an answer can be verified in polynomial time. For the hardest NP problems (i.e., NP-complete problems), given an efficient algorithm for any one of them, we can find an efficient algorithm for all of them [1-4].

The Traveling Salesman Problem (TSP) is the problem of finding a least-cost sequence in which to visit a set of cities, starting and ending at the same city, and in such a way that each city is visited exactly once. This problem has received a tremendous amount of attention over the years due in part to its wide applicability in practice (see [5], for examples). Also, since its seminal formulation as a mathematical programming problem in the 1950's [6], the problem has been at the core of most of the developments in the area of Combinatorial Optimization [7]. A key issue has been the question of whether there exists a polynomial-time algorithm for solving the problem [8].

In this paper, we present a polynomial-sized linear programming formulation of the Traveling Salesman Problem (TSP).

Figure 1. Euler diagram for P, NP, NP-complete, and NP-hard set of problems

2. Solution’s Idea

Let G be the special centroid of triangle , which verifies

We have within the triangle and thus the shortest distance is obtained by connecting to

àTherefore the shortest path is .

It describes the main concept of the solution.

3. Algorithm

Let n be a number of points ; and let be a set of these points.

We want to calculate the minimum distance between these points by returning to the starting point.

Figure 2. Distribution of points for which we want to calculate a minimum distance by returning to the starting point

First, we create a convex polygon that includes all points by the “look left”, method [9].

Creation of convex polygon: look left:

We will examine our points in order, as if we start from one point, and continue by driving around our polygon. The idea is to choose the correct direction so that the interior of the polygon is to the left.

Here is the concept:

A point is inside the polygon if and only if it is "on your left" all along your route. Thus for each orientation as we proceed around the polygon, we examine whether the point being tested is to the left or not. If it is to the right, even once, then the point is not inside.

Determinant:

Mathematically, a simple calculation suffices as the determinant.

We have points .

Let D be the vector

Determining the polygon containing the points of the set where gives :

Thus the convex polygon is as shown in Figure 3.

Figure 3. Creation of convex polygon that includes all points

Thus, let N be the number of points in the convex polygon, and let are the points belonging to the convex polygon.

Let G be the special centroid of the polygon, which verifies:

Figure 4. One point in the triangle

- If is alone in the triangle, then is connected to (Figure 4).

- If there are two points and , 1≤ j ≤ n and 1≤ k ≤ n within the triangle (Figure 5), then:

- If then is connected to .

- Otherwise will be connected to and.

Figure 5. Two points in the triangle

- If there are r points within the triangle we compose the convex polygon between

the points that includes points (Figure 6).

Therefore, there are M points forming a set .

Figure 6. Many points in the triangle , thus we create a new convex polygon within the triangle and its centroid

We are looking for , a centroid of M points, and apply the same method as above (from ) until all point

of triangle are included into the optimal tour, and then proceed to point .

Figure 7. One point in the triangle

Figure 8. Two points in the triangle

-Thus the optimal path is as shown in Figure 9:

Figure 9. Optimal path

4. Discussion

To understand the importance of the P versus NP problem let us imagine a world where P=NP. Technically we could have P = NP, but not have practical algorithms for most NP-complete problems. But suppose in fact we do have very quick algorithms for all these problems.

Many focus on the negative, that if P = NP then public-key cryptography becomes impossible. True, but what we will gain from P = NP will make the whole Internet look like a footnote in history.

Since all the NP-complete optimization problems become easy, everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste.

Learning becomes easy by using the principle of Occam's razor—we simply find the smallest program consistent with the data. Near perfect vision recognition, language comprehension and translation and all other learning tasks become trivial. We will also have much better predictions of weather and earthquakes and other natural phenomenon.

P = NP would also have big implications in mathematics. One could find short, fully logical proofs for theorems but these proofs are usually extremely long. But we can use the Occam razor principle to recognize and verify mathematical proofs as typically written in journals. We can then find proofs of theorems that have reasonable length proofs say in under 100 pages. A person who proves P = NP would walk home from the Clay Institute not with $1 million check but with seven (actually six since the Poincaré Conjecture appears solved).

5. Conclusions

The Travelling Salesman Problem is solvable in polynomial time, and consequently the polynomial solvability of NP-complete problems is stated.

The consequences of this solution are considerable in many areas: cryptology, computer science, mathematics, engineering, economics… The implications of the solution may make the resolution of other problems Millennium trivial.