Aaaaaaaaand… Action! The Optimal Solution to the Travelling Salesman Problem, and a Theory of Everything Ariel Jacobs Physicists and astronomers have been using the principle of least action for decades to accurately predict the movement of matter and EM waves in the universe. In this paper I use various fundamental laws and concepts of physics, culminating with the principle of least action, to arrive at the most efficient deterministic method for finding the shortest closed path through any set of points in 2D or 3D space, thereby solving the Travelling Salesman Problem and creating a bridge between the P and NP complexity classes of problems. Let us suppose a theoretical universe that obeys all the laws of physics, but contains only one electron, one proton, all of 3D space, a source of energy that is able to exert one or more constant or variable forces on the electron, controlling its movement and keeping it from rotating, and another source of energy that is keeping the proton stationary in space and keeping it from rotating, regardless of any forces acting on it. We will assume that both the electron and the proton have spherically symmetric charge distribution. Because the electron has a negative charge and the proton has a positive charge, and neither of them are rotating, and if they are stationary with respect to each other, the resultant electric field vectors created by the two particles will exert a force on the electron pointing toward the proton, and an equal force on the proton pointing toward the electron. This force is called the electrostatic force, and its behavior is defined by Coulomb’s Law. The concept to note from Coulomb’s Law is that the electrostatic force is inversely proportional to the square of the distance between the centers of charge of the two particles. Let us remember that we are keeping the proton stationary in space, so only the electron is able to move with respect to the proton. To arrive at the potential energy of the electron due to its position relative to the proton, we must calculate the negative of the integral of the electrostatic force on the electron over an interval from a distance infinitely far away from the proton to the electron’s current position along a radial path with respect to the center of charge of the proton. I have illustrated this concept in Figure 1 (All figures can be found at the end of this paper). It is important to understand what this means conceptually. This integral, which defines the potential energy of the electron due its position relative to the proton, represents the amount of energy it would take to move the electron from its current position to a distance infinitely far from the proton along a radial path with respect to the center of charge of the proton, at a constant velocity that is infinitely close to zero. Only with a velocity that is infinitely close to zero does Coulomb’s Law apply, and only with a velocity that remains constant throughout the movement of the electron can you state that the force used to move the electron away from the proton is exactly equal and opposite in direction to the electrostatic force at every position along its path. This dual condition of constant velocity that is infinitely close to zero is important not only because it helps to better visualize and understand the concept of potential energy, but also because it will appear with significance later on. Another concept to note for later is that even though the electrostatic force acting on the electron at any position relative to the proton relies on the electron and proton being stationary with respect to each other, the potential energy of the electron at that position is the same regardless of its velocity. One last concept to note before we move on is that because the electron and proton attract one another, the potential energy of the electron due to its location with respect to the proton will always be a negative value. So far we have discussed the potential energy of the electron due to its distance relative to the proton. Another type of energy that the electron can have is kinetic energy, which is energy that is possesses as a result of its motion. One type of kinetic energy is rotational kinetic energy due to the electron rotating. As we discussed earlier, one of our sources of energy is preventing the electron from rotating, so it doesn’t possess any rotational kinetic energy. Another type of kinetic energy is translational kinetic energy, which is the energy that it possesses due its linear motion in space. The value of the translational kinetic energy of the electron is proportional to the square of its velocity, and the equation can be seen in figure 2. Because our electron doesn’t rotate, the total energy of our electron is the sum of its potential energy and translational kinetic energy. This relationship can be seen in figure 2. As mentioned in the previous section, the potential energy of the electron due to its position relative to the proton is independent of the electron’s velocity. An important law in physics is the law of conservation of energy. One consequence of this law is that if no energy is added or removed from a system, the total energy of that system must remain the same. For the purposes of our discussion, we will designate our electron as the ‘system’, and treat it as a closed thermodynamic system, meaning that we cannot add or remove mass, but we can add or remove energy. Just a reminder that the proton in our universe is remaining stationary in space at all times. Figure 3a illustrates the concepts of total energy and conservation of energy. In this example, we are assuming that no external source of energy is able to act on our system. Reminder that the electron is our system. As the electron moves from point A to point B, its total energy will remain constant, because we are not adding or removing any energy. Remember from a previous section that the potential energy will always be negative. Because the magnitude of the potential energy is inversely proportional to the distance of the electron from the proton, and the distance from point A to the proton is greater than the distance from point B to the proton, the magnitude of the potential energy of the electron will be greater at B than at point A. Therefore, it will be a more negative value. Because the total energy remains constant, the kinetic energy must become more positive by the same amount that the potential energy has become more negative. Assuming that the velocity and therefore kinetic energy of the electron at point A is zero, it must have a positive kinetic energy and velocity at point B. If we think about this conceptually, it make sense. Because the proton is exerting an attractive force on the electron at every point in space, if we exert an external force to keep the electron stationary at point A and then remove that external force, the electron will start accelerating towards the proton, so it will have a velocity greater than zero at point B. We have seen from the example in figure 3a that the total energy of the electron remains the same from point A to point B. However, the electron at point B has both a different potential energy and a different kinetic energy than at point A. How do we define this change in the state of our system (the electron)? One function that physicists use to define the state of a physical system at any point in time is called the Lagrangian, named after mathematician Joseph-Louis Lagrange. The Lagrangian is similar to the total energy, yet critically different. Where the total energy is defined as the kinetic energy plus the potential energy, the Lagrangian is defined as the kinetic energy minus the potential energy. Figure 3b refers to the example in figure 3a, but examines the Lagrangian instead of the total energy. We saw that from figure 3a that the total energy of the electron at point A is the same as at point B. However, we can see from figure 3b that the Lagrangian of the electron at point A is different than at point B. In this example, the Lagrangian of our system changes by an amount exactly equal to the magnitude of the change in kinetic energy plus the magnitude of the change in potential energy. In general, we can see that because the potential energy of the electron will always be a negative value, the Lagrangian will always be the kinetic energy plus the magnitude of the potential energy. The fact that the Lagrangian changes with a change in kinetic and/or potential energy makes it a comprehensive single-value definition of the state of a physical system at any point in time. As the Lagrangian defines the state of a physical system at any point in time, it only makes sense that integrating the Lagrangian over a spacetime interval will give us a single- value description of the physical system during that spacetime interval. A spacetime interval is defined by a change in time and any change in location of the system in 3D space during that change in time. For our system, which is the electron, a spacetime interval would be a change in time and any change in location of the electron during that change in time. The function that defines the integral of the Lagrangian of a system over a spacetime interval is called the action, and can be seen in figure 4. For the system we are considering in our discussion, we can see the specific action integral. Expectedly, this integral contains the kinetic and potential energies of the electron. If you remember at the beginning we discussed the principle of least action. This principle states that the path taken by a system under a given set of conditions will be the one whose action is the smallest in magnitude, therefore the principle of least action. Each path is defined by a different spacetime interval. For decades, physicists and astronomers have confided in this principle to accurately predict the movement of matter and EM waves in the universe. In the intro I mentioned that we will be using the principle of least action to find the shortest closed path through any set of points in 2D or 3D space, which is the goal of the Travelling Salesman Problem. How though, can we apply the principle of least action to our universe, with the one electron and one proton, to solve the Travelling Salesman Problem? Well, first we will use the given set of points as the locations that our electron must travel to. As we discussed earlier, in our universe, the electron is allowed to move, but the proton must remain stationary. Remember that the action of the electron for any given spacetime interval, or path, is dependent upon its kinetic energy and potential energy. The potential energy of the electron depends on its location relative to the proton. Therefore, if we change the location of our proton, the action of the electron for any given path will be different. This means that the location of our proton is extremely crucial to solving the Travelling Salesman Problem. But where do we place the proton? Well, every point in the given set of points has the exact same conditions and restrictions, because each point must be visited once and only once in the closed path. Furthermore, the addition to the overall length of the closed path due to traveling between any two points is exactly equal to the Euclidean distance between the two points. Therefore, each point is equally significant and all distances between any two points are equally weighted. Furthermore, because we are assuming the electron and proton both have spherically symmetric charge distribution, the electric field created by each of these particles also exhibits spherical symmetry. Therefore, it would only be correct to place the proton in the geometric center of all the points. Now that we know where our proton will be placed relative to the points that the electron must visit, do we have enough information to calculate the action of the electron traveling between any two points? The answer is not yet. The reason is that we still haven’t decided on the behavior of the velocity of the electron during its movement. As we see in figure 5, the integral for the action of the electron during any spacetime interval can be restated as the sum of two separate integrals. Both of these integrals, which I have designated as A and A , are dependent on the behavior of the velocity of the T U electron during its movement. Integral A is integrating the kinetic energy, which is T proportional to the square of the velocity, so it consequently depends on the velocity. More subtle, but just as significant, is the fact that Integral A also depends on the U velocity, because we are integrating over a spacetime interval, and the time portion of that interval will depend on the behavior of the velocity. Therefore, what conditions can we place on the velocity of the electron such that we will be able to calculate the action of the electron during its path from one point to another? It turns out that there are two conditions that we both can, and must place on the velocity of the electron. These two conditions will allow us to not only ignore integral A , but also calculate integral A , therefore allowing T U us to calculate the much desired action integral. We have seen these two conditions before, and I think everybody knows where this is going. The electron must have a constant velocity that is infinitely close to zero. With a velocity that is constant and infinitely close to zero, integral A will be infinitely close to zero and can therefore be T disregarded completely. Only with a velocity that remains constant throughout the movement of the electron can we calculate integral A . More precisely, we can only U calculate a value that differs from the exact value of integral A by a factor, but the crucial U concept is that as long as the velocity remains constant throughout the journey of the electron, that factor will be equal for all our action calculations. Because we will eventually be making decisions based on how the action values compare against one another, it won’t matter that we are off by a common factor. Figure 6 illustrates our ability to calculate a factor of integral A given a constant velocity of the electron. As you can U see from the figure, the reason there is a factor separating our calculated value from the actual value of integral A is that we don’t know the exact value of the electron’s velocity, U and therefore we can’t calculate the exact amount of time it takes to get from point A to point B; we only know that the amount of time is directly proportional to the distance between the two points because the velocity remains constant. Furthermore, we can remove the values of the electron’s charge, proton’s charge, and Coulomb’s constant from our calculations, because they will also remain constant and will therefore only contribute to the value of the common factor. Because we are removing a common factor from our action calculations, we will from here on refer to our calculated values as the relative action, as opposed to the absolute action. As mentioned previously, for the purposes of solving the Travelling Salesman Problem, we only need to know how our action values compare to one another; their absolute values are irrelevant. Therefore, because all our calculations will be off by the same factor, the relative action is fully sufficient. Figure 7 shows the final equation for the relative action of moving the electron at a constant velocity between any two points in 3D space, relative to the proton. In words, we are integrating the potential energy of the electron over the spacetime interval that defines the electron’s journey from point A to point B. More specifically, we are integrating the potential energy of the electron over the space through which it travels from point A to point B, and then multiplying that value by the relative time it takes to get from point A to point B. I say relative time because we are actually multiplying by the distance from point A to point B, which is proportional to the time it takes to get from point A to point B because of the constant velocity. It is important to note that our relative action equation is only such because of our theoretical universe containing only one electron and one proton, and the specific conditions we are placing on the electron and proton. Any other conditions would yield a different equation for the relative action. One concept to note is that the relative action of the electron going from point A to point B will be identical to the relative action of the electron going from point B to point A. Let us consider the spacetime interval between any two points A and B to be a possible segment of the closed path that the electron will travel. For any given set of points in 2D or 3D space with n number of points, there will be (n*(n-1))/2 number of different segments and therefore (n*(n-1))/2 number of different relative action values, because there is exactly one unique relative action value for every segment. Once again, this is because the relative action from point A to point B is the same as the relative action from point B to point A. We discussed in the beginning that our universe contains a source of energy that is able to exert any constant or variable amount of force on the electron in any direction. We discussed recently why, in order for us to solve the Travelling Salesman Problem, our electron must not only move at a constant velocity, but also be able to move between any two points in 2D or 3D space, relative to the stationary proton. If we remember from our example in Figure 3a, the total energy of the electron remains constant, meaning we are not able to act on the electron with any external force, causing the movement of the electron to be limited to only one option. Assuming the electron has a velocity of zero at point A, it will begin accelerating towards the proton along a radial path, reaching point B after some amount of time. Therefore, because in this example we are not able to act on the electron with any external force, not only can the electron not move with a constant velocity, but also its course of movement is limited to only one option. As soon as we add a source of energy to our universe that is able to act on the electron with one or more constant or variable forces in any direction, we allow our electron the ability to move with constant velocity between any two points in 2D or 3D space, relative to the proton. Note that in our situation, a change in total energy of the electron will result only from a change in its potential energy, because the electron’s velocity and therefore kinetic energy will remain constant. So far we have only discussed the environment, the conditions, and the calculations that will give us our relative action values for an electron moving at constant velocity between any two points in 3d space, relative to the proton. To help explain the remainder of the steps in the algorithm that will eventually give us the shortest closed path through any set of points in 2D or 3D space, I will from here on refer to a sample set of points that can be found in the ‘National TSP Collection’ hosted by the Math Department at the University of Waterloo in Ontario, Canada. This is a set of 38 points in 2D space that define the relative locations of 38 cities in the country of Djibouti. Similar to how Figure 7 shows the equation for the relative action of moving the electron at a constant velocity between any two points in 3D space, relative to the proton, Figure 8 shows the equation for the relative action of moving the electron at a constant velocity between any two points in 2D space, relative to the proton. As you can see, the only difference between these two equations is the expression of the indefinite integral I(p). Whereas the spacetime interval in the integral in Figure 7 contains three dimensions of space, the spacetime interval in the integral in Figure 8 contains two dimensions of space, thereby causing I(p) in Figure 8 to be a reduced version of I(p) in Figure 7. Figure 9 shows the 2D coordinates of the 38 points from the Djibouti data set. Also, I will from here on refer to the shortest closed path through a set of points as the optimal route. Figure 10 shows the 38 points identified by green ‘+’ markers, and the coordinates are relative to the proton. The red ‘x’ marker identifies the location at which we will place our proton so that we can find the optimal route for our electron, and it can be seen at the origin. As discussed previously, this location is the geometric center of the 38 points. Once we have calculated the location of our proton, we will calculate the relative action values for all possible segments in this set of points. As discussed previously, there will be (n*(n-1))/2 different segments and therefore (n*(n-1))/2 different relative action values. In our example, there are 38 different points, and therefore (38*37)/2 = 703 different segments and relative action values. Therefore, we have to perform 703 different relative action calculations. Figure 11 shows the relative action calculation that will be performed between points 1 and 2. Once we have calculated our 703 relative action values, we will first determine the top two segments containing each of the points in the data set. The top two segments for each point will be the two segments that contain that point and have the smallest relative action values. Once we have determined the top two segments for all the points and then removed any duplicates from that list, we will add those segments to our graph shown in Figure 10. Figure 12 shows a list of those segments. At this time, we will check if at least one closed path exists that contains all the points. If only one such path exists, then that path is our optimal route. If more than one closed path exists that contains all the points, our optimal route will be the closed path with the smallest combined relative action value. To calculate the combined relative action value of each closed path, we simply add together the relative action values of all the segments in each closed path. If no closed path exists that contains all the points, we will begin adding remaining segments one by one to our graph in order of ascending relative action value. As we add segments to our graph, we will eventually create one or more closed paths that contains all the points. Figure 13 shows the top two segments for all points added to our graph, and we can already see multiple closed paths: one defined by points 10, 14 and 21, one defined by points 29, 30, and 32, and another defined by points 31, 34, and 36, as well as others. However, none of these closed paths match the condition of the Travelling Salesman Problem, which requires the closed path to contain all the points. Therefore, we must begin adding additional segments, in order of ascending relative action value, to our graph until we have at least one closed path that contains all the points. Figure 14 shows the minimum number of segments required to define at least one closed path through all the points. In this case, the last segment that was added was the segment defined by points 15 and 20. As we can see from Figure 14, adding this segment has brought us from having no closed path defined by all the points to having multiple closed paths defined by all the points. In this situation, our optimal route will be the closed path with the smallest combined relative action value. As mentioned previously, to calculate the combined relative action value of each closed path, we simply add together the relative action values of all the segments in each closed path. Figure 15 shows the optimal route for our example and Figure 16 shows the list of segments in the optimal route. This algorithm, which provides the most efficient deterministic method for finding the shortest closed path through any set of points in 2D or 3D space, will be known as Ariel’s Algorithm. One exciting fact to note is that the closed path with the smallest combined relative action value is the same as the closed path with the smallest total distance. Another exciting concept is that this discovery directly implies that Coulomb’s observation that the electrostatic force between two point charges is inversely proportional to the square of the distance between the charges is in fact an underlying physical reality. Another exciting concept to note is that if you create a ray for each point, starting at the location of the proton and extending through each of the points in the data set, and then offset the distance of each point from the proton along its corresponding ray by a factor common to all the points, the values of [ I(s) – I(0) ] for all new segments will be identical to those of the previous segments. The value that will change will be s, and it will be subject to the common factor. Therefore, because A = [ I(s) – I(0) ]*s, the relative action R values of the new segments will similarly be offset by the common factor. Importantly, because all the relative action values will be offset by the same factor, we will arrive at the same optimal route. Changing the distances of the points relative to the proton by a common factor, along rays originating at the proton, provides us with the identical optimal route. One very significant aspect of this algorithm is its behavior with respect to time complexity. The universal governing and definitive nature of the principle of least action allows our algorithm to have the smallest possible time complexity for any set of points in 2D or 3D space. There are two components of our algorithm that contribute to its time complexity for any set of points. The first component we will refer to as the common component, because its time complexity is the same for any set of points. This component consists of calculating the relative action values for all possible segments (time complexity O(n2)), determining the top two segments for all the points (time complexity O(n*log(n)) for each point and therefore O(n2*log(n)) for all points), and then removing any duplicates from the list of top two segments (time complexity O(n2)). The limiting step in this sequence is determining the top two segments for all the points, and therefore the time complexity for the entire common component is O(n2*log(n)). The second component of our algorithm that contributes to its overall time complexity we will refer to as the unique component, because it is unique to a specific set of points, and it is due to checking if at least one closed path exists that contains all the points, and if not, adding remaining segments, in order of ascending relative action value, until at least one closed path exists that contains all the points. If adding the final necessary segment creates more than one closed path that contains all the points, we must also calculate and compare the combined relative action values of those closed paths, which is what we had to do in the example with the Djibouti data set. The most ideal situation for our unique component and therefore for our entire algorithm would be if all the points in our data set were on a circle, because then our unique component would execute in linear time, meaning it would have a time complexity of O(n). Our Djibouti data set does not lie on a circle and therefore the unique component took longer than linear time, but the significance is that our algorithm determined the optimal route with the smallest possible time complexity given that specific set of points. The fact that our algorithm will always arrive at the optimal route as efficiently as possible for any set of points is a consequence of the beauty and definitive nature of the principle of least action. With regards to the question of P vs. NP, our algorithm is a deterministic algorithm that solves the Travelling Salesman Problem with the smallest possible time complexity given any set of points. Best case scenario, as mentioned above, with all the points on a circle, our algorithm will execute within polynomial time, with time complexity O(n2*log(n)), which is faster than O(n3). Given any other set of points, our algorithm may execute with a time complexity greater than O(n2*log(n)), but the principle of least action will always force it to execute with the smallest time complexity possible. The significance here is that physics has allowed us to discover the optimally efficient deterministic algorithm to solve a problem that was previously considered to not be solvable by a deterministic algorithm in a reasonable amount of time. Physics has allowed us to discover a bridge between the P and NP complexity classes. To solve the Travelling Salesman Problem, we discussed a universe that contained only one electron, one proton, and two other sources of energy, one to control the movement of the electron, and the other to keep the proton stationary. However, in our actual universe, there are many electrons and many protons that are allowed to move and rotate freely, and many sources of energy. The principle of least action has been used for decades to predict the movement of matter and EM waves in the universe, and the discovery of our algorithm has demonstrated another example of this principle’s significance. If you remember at the beginning we discussed Coulomb’s Law and the electrostatic force created by the electric fields of particles with spherically symmetric charge distribution that are stationary with respect to each other. In our universe, in which all charged particles have a kinetic energy greater than zero, all charged particles create both electric fields and magnetic fields, referred to together as electromagnetic fields. These electromagnetic fields exert electromagnetic force on other charged particles and interact with other electromagnetic fields. Now what if the electromagnetic fields are the only physical fields, and the electromagnetic force is the only fundamental force that exists in our universe? What if the apparent forces of gravity, the strong interaction, and the weak interaction are all solely due to electromagnetic forces throughout our universe, on both a very large and a very small scale? What about if the only elementary particles that exist in our universe are electrons and protons, and there are no such things as quarks, bosons, neutrinos, etc.? What if there are no such things as dark matter, antimatter, etc.? What if a neutron is actually just a composition of a proton and an electron, and the asymmetry of the negative and positive charge distribution in a proton-electron configuration allows for a portion of the surrounding space throughout which exist resultant electric field vectors that point toward the neutron, allowing it to behave as a negatively charged composite particle? Wouldn’t that explain why the mass of a neutron is slightly greater than that of a proton? Wouldn’t that explain why the magnetic dipole moment of a neutron is approximately 1/1000 of the sum of the proton magnetic dipole moment and electron magnetic dipole moment (due to the size difference of the electron and proton), and is negative, similar to the electron’s magnetic dipole moment? And wouldn’t the net negative magnetic dipole moment and effective negative charge of the neutron contribute to why neutrons and protons can stay attracted to each other in a stable configuration to form nuclei? When you sum the magnetic dipole moments of a proton and a neutron, you get a positive net magnetic dipole moment, and the asymmetry of the negative and positive charge distribution in a proton-neutron configuration allows for a portion of the surrounding space throughout which exist resultant electric field vectors that point away from the proton-neutron configuration. Wouldn’t those two facts contribute to why electrons can stay attracted to nuclei in a stable configuration to form atoms? And wouldn’t a relatively lower strength of electromagnetic forces existing in the space surrounding matter vs. the space containing matter, in addition to the charge distribution asymmetries and magnetic moments throughout each atom, contribute to why atoms can stay attracted to each other in a stable configuration to form molecules, compounds, etc? And doesn’t all matter essentially consist of charged particles that are affected by and contribute to the surrounding electromagnetic fields created not only by the other particles in that matter but also by other matter throughout the universe? And wouldn’t this